鏈表的操作

鏈表中的插入（頭插）

void *insertNode(ListNode *head, ListNode *node) {node->next = head;head = node;return; }

鏈表中的插入（尾插）

void *insertNode(ListNode *head, ListNode *node) {ListNode *front = head;while(head) {// 備份前一個(gè)節(jié)點(diǎn)front = head;head = head->next;}front->next = node;return; }

鏈表中的插入

void *insertNode(ListNode *head, ListNode *node) {// 插入到結(jié)點(diǎn)7之后while(head&&!head->val==7) head = head->next;// 先將結(jié)點(diǎn)7下一個(gè)結(jié)點(diǎn)的地址賦值給node的指針node->next = head->next;// 將node作為下一個(gè)結(jié)點(diǎn)head->next = node;return; }

鏈表中的刪除

void *deleteNode(ListNode *head, ListNode *node) {ListNode *front = head;while(head&&!head==node) {// 備份前一個(gè)節(jié)點(diǎn)front = head;head = head->next;}front->next = head->next;return; }

鏈表中的查找

bool *deleteNode(ListNode *head, int value) {while(head&&!head->val==value) {head = head->next;}if(head==NULL) return false; // 沒找到else return true; // 找到了 }

鏈表操作的一些技巧

鏈表精髓在于指針移動

特別注意 空指針 時(shí)的情況，無論開頭還是結(jié)尾都要考慮，尤其是 p->next == NULL ? 要特別注意

類型一：反轉(zhuǎn)數(shù)列

ListNode *reverseList(ListNode *head, int mid) {ListNode *newHead = NULL;while(mid--) {// 備份主鏈的下一個(gè)節(jié)點(diǎn) ListNode *node = head->next;// 更新head的next指針，指向子鏈頭指針 head->next = newHead;// 更新子鏈頭指針 newHead = head;// 更新主鏈頭指針 head = node;}return newHead; }

類型二：快慢指針

第幾第幾這種可以使用快慢指針或者雙指針

ListNode *detectCycle(ListNode *head) {ListNode *fast = head;ListNode *slow = head;ListNode *meet = NULL;while(fast&&fast->next&&fast->next->next) {fast = fast->next->next;slow = slow->next;if(fast==slow) {meet = fast;break;}}if(fast==NULL||fast->next==NULL||fast->next->next==NULL) {return NULL;}while (head) {if(meet == head) {return meet;}meet = meet -> next;head = head -> next;}return NULL; }

類型三：巧設(shè)頭指針

ListNode* partition(ListNode* head, int x) {ListNode frontHead(0);ListNode afterHead(0);ListNode *front = &frontHead;ListNode *after = &afterHead;while (head) {if (head->val < x) {front -> next = head;front = head;} else {after -> next = head;after = head;}head = head -> next;}front->next= afterHead.next;after->next = NULL;return frontHead.next; }

類型四：創(chuàng)建新節(jié)點(diǎn)

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {// 巧設(shè)頭結(jié)點(diǎn) ListNode a(0);ListNode *ans = &a;int carry = 0;ListNode *p = NULL; // 精髓while(l1&&l2) {int num = l1->val+l2->val + carry;if(num>=10){int rest = num % 10;carry = 1;p = new ListNode(rest); // 精髓ans->next = p;// 移動ans指針 ans = p; } else {carry = 0;p = new ListNode(num);ans->next = p;// 移動ans指針 ans = p; } l1 = l1->next;l2 = l2->next;}while(l1) {int num = l1->val + carry;if(num>=10){int rest = num % 10;carry = 1;p = new ListNode(rest);ans->next = p;// 移動ans指針 ans = p; } else {carry = 0;p = new ListNode(num);ans->next = p;// 移動ans指針 ans = p; } l1 = l1->next;}while (l2) {int num = l2->val + carry;if(num>=10){int rest = num % 10;carry = 1;p = new ListNode(rest);ans->next = p;// 移動ans指針 ans = p; } else {carry = 0;p = new ListNode(num);ans->next = p;// 移動ans指針 ans = p; } l2 = l2->next;}return a.next; }

雙鏈表

為了克服單鏈表的上述缺點(diǎn)，引入了雙鏈表，雙鏈表結(jié)點(diǎn)中有兩個(gè)指針 front 和 next，分別指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)

雙鏈表的插入

// 將node插入到head之后 node->next = head->next; // ① head->next->front = node; // ② node->front = head; // ③ head->next = node; // ④

雙鏈表的刪除

head->next = node->next; // ① node->next->front = head; // ②

循環(huán)鏈表

循環(huán)單鏈表：循環(huán)單鏈表和單鏈表的區(qū)別在于，表中最后一個(gè)結(jié)點(diǎn)的指針不是NULL，而改為指向頭結(jié)點(diǎn)，從而整個(gè)鏈表形成一個(gè)環(huán)

循環(huán)雙鏈表：由循環(huán)單鏈表的定義不難推出循環(huán)雙鏈表，不同的是在循環(huán)雙鏈表中，頭結(jié)點(diǎn)的 prior指針還要指向表尾結(jié)點(diǎn)

在循環(huán)雙鏈表工中，某結(jié)點(diǎn)*p為尾結(jié)點(diǎn)時(shí)，p->next==L; 當(dāng)循環(huán)雙鏈表為空表時(shí)，其頭結(jié)點(diǎn)的 front 域和 next 域都等于 L。

總結(jié)

以上是生活随笔為你收集整理的【数据结构-线性表】顺序表和链表（几种链表操作技巧+几种链表形式）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。