?個人主頁：bit me
?當(dāng)前專欄：算法基礎(chǔ)
??專欄簡介：該專欄主要更新一些基礎(chǔ)算法題，有參加藍(lán)橋杯等算法題競賽或者正在刷題的鐵汁們可以關(guān)注一下，互相監(jiān)督打卡學(xué)習(xí) ?? ?? ??
實現(xiàn)一個單鏈表，鏈表初始為空，支持三種操作：
- 向鏈表頭插入一個數(shù)；
- 刪除第 k 個插入的數(shù)后面的數(shù)；
- 在第 k 個插入的數(shù)后插入一個數(shù)。
現(xiàn)在要對該鏈表進(jìn)行 M 次操作，進(jìn)行完所有操作后，從頭到尾輸出整個鏈表。
注意:
題目中第 k 個插入的數(shù)并不是指當(dāng)前鏈表的第 k 個數(shù)。例如操作過程中一共插入了 n 個數(shù)，則按照插入的時間順序，這 n 個數(shù)依次為：第 1 個插入的數(shù)，第 2 個插入的數(shù)，…第 n 個插入的數(shù)。
輸入格式：
第一行包含整數(shù) M，表示操作次數(shù)。
?
接下來 M 行，每行包含一個操作命令，操作命令可能為以下幾種：
?
- H x，表示向鏈表頭插入一個數(shù) x。
- D k，表示刪除第 k 個插入的數(shù)后面的數(shù)（當(dāng) k 為 0 時，表示刪除頭結(jié)點）。
- I k x，表示在第 k 個插入的數(shù)后面插入一個數(shù) x（此操作中 k 均大于 0）。
輸出格式：
共一行，將整個鏈表從頭到尾輸出。
數(shù)據(jù)范圍：
1≤M≤100000
?
所有操作保證合法。
輸入樣例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
輸出樣例：
6 4 6 5
思路：文章來源：http://www.zghlxwxcb.cn/news/detail-416465.html
- 第一個操作：刪除頭結(jié)點，我們可以直接弄一個第三方，然后輪流轉(zhuǎn)移賦值即可，前面鏈表文章寫了很多
- 第二步和第一步一樣的操作
- 第三個操作就直接讓他等于下一個節(jié)點就行
- 向鏈表頭插入一個數(shù)；
public static void add_head(int x){
e[index] = x;
ne[index] = head;
head = index++;
}
- 刪除第 k 個插入的數(shù)后面的數(shù)；
public static void remove(int k){
ne[k] = ne[ne[k]];
}
- 在第 k 個插入的數(shù)后插入一個數(shù)。
public static void add(int k,int x){
e[index] = x;
ne[index] = ne[k];
ne[k] = index++;
}
- 主函數(shù)對他們的分類操作
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
init();//初始化
while(m -- > 0){
//因為java中沒有輸入一個字符，所以用字符串轉(zhuǎn)字符
String s = scan.next();
char op = s.charAt(0);
if(op == 'H'){
int x = scan.nextInt();
add_head(x);
}else if(op == 'D'){
int k = scan.nextInt();
if(k == 0) head = ne[head];
else remove(k-1);
}else {
int k = scan.nextInt();
int x = scan.nextInt();
add(k-1,x);
}
}
for(int i = head;i != -1;i = ne[i] ){
System.out.print(e[i] + " ");
}
}
附上總的代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-416465.html
public class Demo3 {
static int[] e = new int[100010];
static int[] ne = new int[100010];
static int index,head;
public static void init(){
index = 0;
head = -1;
}
//H向鏈表頭插入一個數(shù)x；
public static void add_head(int x){
e[index] = x;
ne[index] = head;
head = index++;
}
//I在第k位數(shù)后面插入一個數(shù)x
public static void add(int k,int x){
e[index] = x;
ne[index] = ne[k];
ne[k] = index++;
}
//D刪除第k個數(shù)后面得數(shù)
public static void remove(int k){
ne[k] = ne[ne[k]];
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
init();//初始化
while(m -- > 0){
//因為java中沒有輸入一個字符，所以用字符串轉(zhuǎn)字符
String s = scan.next();
char op = s.charAt(0);
if(op == 'H'){
int x = scan.nextInt();
add_head(x);
}else if(op == 'D'){
int k = scan.nextInt();
if(k == 0) head = ne[head];
else remove(k-1);
}else {
int k = scan.nextInt();
int x = scan.nextInt();
add(k-1,x);
}
}
for(int i = head;i != -1;i = ne[i] ){
System.out.print(e[i] + " ");
}
}
}
到了這里，關(guān)于【算法基礎(chǔ)】(二)數(shù)據(jù)結(jié)構(gòu) --- 單鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
