常見算法：

1.鏈表逆序

2.鏈表求交點

3.鏈表求環(huán)

4.鏈表劃分

5.復(fù)雜鏈表的復(fù)制

6-a.2個排序鏈表歸并

6-b.k個排序鏈表歸并

?

---

?鏈表定義：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/

?

1.鏈表逆序

class Solution { public:ListNode* reverseList(ListNode* head) {ListNode *next=NULL; ListNode *new_head=NULL; while(head){ next=head->next; head->next=new_head; new_head=head; head=next; } return new_head; } };

new_head是新鏈表的頭指針，next是為了記錄下一個要反轉(zhuǎn)的結(jié)點指針。

---

?

2.鏈表求交點

class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {std::set<ListNode*> node_set;while(headA){node_set.insert(headA);}while(headB){if(node_set.find(headB)!=node_set.end()){return headB;}}return NULL;} }

用stl 的set，時間復(fù)雜度nlogn，判定超時

int get_length(ListNode *head){int len=0;while(head){len++;head=head->next;}return len; } ListNode * get_same_node(int long_len,int short_len,ListNode *head){int delta=long_len-short_len;while(delta--){head=head->next;}return head; } class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int len_A=get_length(headA);int len_B=get_length(headB);if(len_A>len_B){headA=get_same_node(len_A,len_B,headA);}else{headB=get_same_node(len_B,len_A,headB);}while(headA){if(headA==headB){return headA;}headA=headA->next;headB=headB->next;}return NULL;} };

先求出兩個鏈表長度，然后對齊指針。時間復(fù)雜度O（n）

---

?3.鏈表求環(huán)

class Solution { public:bool hasCycle(ListNode *head) {ListNode *fast=head;ListNode *slow=head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow) return true;}return false;} };

快慢指針。

---

?

4.劃分鏈表

class Solution { public:ListNode* partition(ListNode* head, int x) {ListNode moreNode(0),lessNode(0);ListNode *more=&moreNode,*less=&lessNode;while(head){if(head->val < x){less->next=head;less=head; }else{more->next=head;more=head;}head=head->next;} less->next=moreNode.next;more->next=NULL;//注意尾指針清空！！！return lessNode.next;} };

利用兩個頭節(jié)點掛上多于x和少于x的節(jié)點，最后修改指針，注意尾指針需要清空。

---

?

5.復(fù)雜鏈表的復(fù)制

?

class Solution { public:RandomListNode *copyRandomList(RandomListNode *head) {if(head==NULL) return NULL;unordered_map<RandomListNode*,RandomListNode*> m;RandomListNode headNode(0);RandomListNode *cur=&headNode;RandomListNode *old_cur=head;while(old_cur){RandomListNode *temp=new RandomListNode(old_cur->label);cur->next=temp;m.insert({old_cur,temp});cur=cur->next;old_cur=old_cur->next;}cur->next=NULL;cur=headNode.next;old_cur=head;while(cur){cur->random=m[old_cur->random];cur=cur->next;old_cur=old_cur->next;}return headNode.next;} };

old_cur為原鏈表的遍歷指針，cur為新鏈表的遍歷指針

?

---

?6-a.2個排序鏈表的歸并

class Solution { public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode head(0);ListNode *p=&head;while(l1 && l2){if(l1->val <= l2->val){p->next=l1;l1=l1->next;}else{p->next=l2;l2=l2->next;}p=p->next;}if(l1==NULL) p->next=l2;if(l2==NULL) p->next=l1;return head.next; }};

?6-b.k個排序鏈表合并

class Solution { public:ListNode* mergeKLists(vector<ListNode*>& lists) {int len=lists.size();if(len==0) return NULL;if(len==1) return lists[0];if(len==2) return mergeTwoLists(lists[0],lists[1]);int mid=len/2;vector<ListNode *> sub_list1,sub_list2;for(int i;i<mid;i++){sub_list1.push_back(lists[i]);}for(int i=mid;i<len;i++){sub_list2.push_back(lists[i]);}ListNode *l1=mergeKLists(sub_list1);ListNode *l2=mergeKLists(sub_list2);return mergeTwoLists(l1,l2);} };

mergeTwoLists函數(shù)是上面的。時間復(fù)雜度O(nklogk).

---

?

其他算法題型：

1.刪除指定節(jié)點　

class Solution { public:void deleteNode(ListNode* node) {node->val=node->next->val;node->next=node->next->next;} };

給定的是要刪除的節(jié)點的指針，要刪除該節(jié)點，由于無法獲取前面節(jié)點的next，無法通過修改該next指向后面的節(jié)點。

這里將該節(jié)點的值用其后面節(jié)點的值替換，再刪除后面的節(jié)點，達到等效的作用。

2.獲取中間節(jié)點

　　描述：給定一個帶有頭結(jié)點?head?的非空單鏈表，返回鏈表的中間結(jié)點。如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。

class solution{public:ListNode *getMiddleNode(ListNode *head){ListNode *fast=head;ListNode *slow=head;while(fast != NULL && fast->next != NULL){fast=fast->next->next;slow=slow->next;}return slow;} }

快慢指針法。

另一種是將節(jié)點指針輸入到數(shù)組，再利用數(shù)組的隨機訪問特性。而隨機訪問正是鏈表的弱點。

?

轉(zhuǎn)載于:https://www.cnblogs.com/chendaniu/p/10208002.html

總結(jié)

以上是生活随笔為你收集整理的算法-链表常用算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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