- 删除链表中的节点:1.通过找前一个节点
2.通过找后一个节点然后把当前节点伪装成后一个
void deleteNode(ListNode* node) { node->val = node->next->val; node->next = node->next->next; }
- 数组模拟单链表:
1 实现一个单链表,链表初始为空,支持三种操作: 2 3 (1) 向链表头插入一个数; 4 5 (2) 删除第k个插入的数后面的数; 6 7 (3) 在第k个插入的数后插入一个数 8 9 现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。 10 11 注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。 12 13 输入格式 14 第一行包含整数M,表示操作次数。 15 16 接下来M行,每行包含一个操作命令,操作命令可能为以下几种: 17 18 (1) “H x”,表示向链表头插入一个数x。 19 20 (2) “D k”,表示删除第k个输入的数后面的数(当k为0时,表示删除头结点)。 21 22 (3) “I k x”,表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。 23 24 输出格式 25 共一行,将整个链表从头到尾输出。 26 27 数据范围 28 1≤M≤100000 29 所有操作保证合法。 30 31 输入样例: 32 10 33 H 9 34 I 1 1 35 D 1 36 D 0 37 H 6 38 I 3 6 39 I 4 5 40 I 4 5 41 I 3 4 42 D 6 43 输出样例: 44 6 4 6 5 45 46 #include <iostream> 47 48 using namespace std; 49 50 const int N = 1e5+10; 51 52 int e[N] = {0}; 53 int ne[N] = {0}; 54 int idx;//当前可用下标 55 int head; 56 57 void init(){ 58 head = -1; 59 idx = 0; 60 } 61 62 void insert_head(int x){ 63 e[idx] = x; 64 ne[idx] = head; 65 head = idx ++ ; 66 } 67 //在下标为index的后面插入一个数x 68 void add(int index,int x){ 69 e[idx] = x; 70 ne[idx] = ne[index]; 71 ne[index] = idx ++; 72 } 73 74 //删除下标为k的后面的数 75 void del(int k){ 76 ne[k] = ne[ne[k]]; 77 } 78 79 int main(){ 80 int m; 81 cin >> m; 82 init(); 83 84 while(m --){ 85 int k, x; 86 char op; 87 cin >> op; 88 switch(op){ 89 case 'H': 90 cin >> x; 91 insert_head(x); 92 break; 93 case 'D': 94 cin >> k; 95 if(k == 0)head = ne[head]; 96 else del(k-1); 97 break; 98 case 'I': 99 cin >> k >> x; 100 add(k-1,x); 101 break; 102 default: 103 break; 104 } 105 } 106 for(int i = head;i != -1;i = ne[i])cout << e[i] << " "; 107 return 0; 108 }
- 数组模拟双链表
1 实现一个双链表,双链表初始为空,支持5种操作: 2 3 (1) 在最左侧插入一个数; 4 5 (2) 在最右侧插入一个数; 6 7 (3) 将第k个插入的数删除; 8 9 (4) 在第k个插入的数左侧插入一个数; 10 11 (5) 在第k个插入的数右侧插入一个数 12 13 现在要对该链表进行M次操作,进行完所有操作后,从左到右输出整个链表。 14 15 注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。 16 17 输入格式 18 第一行包含整数M,表示操作次数。 19 20 接下来M行,每行包含一个操作命令,操作命令可能为以下几种: 21 22 (1) “L x”,表示在链表的最左端插入数x。 23 24 (2) “R x”,表示在链表的最右端插入数x。 25 26 (3) “D k”,表示将第k个插入的数删除。 27 28 (4) “IL k x”,表示在第k个插入的数左侧插入一个数。 29 30 (5) “IR k x”,表示在第k个插入的数右侧插入一个数。 31 32 输出格式 33 共一行,将整个链表从左到右输出。 34 35 数据范围 36 1≤M≤100000 37 所有操作保证合法。 38 39 输入样例: 40 10 41 R 7 42 D 1 43 L 3 44 IL 2 10 45 D 3 46 IL 2 7 47 L 8 48 R 9 49 IL 4 7 50 IR 2 2 51 输出样例: 52 8 7 7 3 2 9 53 54 55 #include <iostream> 56 57 using namespace std; 58 59 const int N = 1e5+10; 60 61 int e[N];//当前结点的值 62 int l[N];//当前结点的左面的下标 63 int r[N];//当前结点的右边的下标 64 int idx;//新插入的节点的可用位置 65 66 void init(){ 67 l[1] = 0, r[0] = 1; 68 idx = 2; 69 } 70 //在x的右边插入一个数a 71 void insert(int x, int a){ 72 e[idx] = a; 73 l[idx] = x; 74 r[idx] = r[x]; 75 76 l[r[idx]] = idx; 77 r[x] = idx ++; 78 } 79 80 //删除节点x 81 void del(int x){ 82 r[l[x]] = r[x]; 83 l[r[x]] = l[x]; 84 } 85 86 int main(){ 87 init(); 88 int m; 89 cin >> m; 90 while (m -- ) 91 { 92 string op; 93 cin >> op; 94 int k, x; 95 if (op == "L") 96 { 97 cin >> x; 98 insert(0, x); 99 } 100 else if (op == "R") 101 { 102 cin >> x; 103 insert(l[1], x); 104 } 105 else if (op == "D") 106 { 107 cin >> k; 108 del(k + 1); 109 } 110 else if (op == "IL") 111 { 112 cin >> k >> x; 113 insert(l[k + 1], x); 114 } 115 else 116 { 117 cin >> k >> x; 118 insert(k + 1, x); 119 } 120 } 121 122 for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' '; 123 cout << endl; 124 125 return 0; 126 127 } 128 129
end