【 數(shù)據(jù)結(jié)構(gòu) & 算法 】 —— 鏈表

< 思維導(dǎo)圖 >

預(yù)備知識(shí)：鏈表基礎(chǔ) (★)

鏈表全部逆序 (★)

  • LeetCode 206. Reverse Linked List.cpp
#include <stdio.h>

struct ListNode{ 
    int val; // 數(shù)據(jù)域
    ListNode *next; // 指針域       
    // 構(gòu)造函數(shù)
    ListNode(int x) : val(x), next(NULL) { }
};
class Solution{
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *new_head = NULL;
        while(head){
            ListNode *next2 = head->next; // 備份 head->next
            head->next = new_head; // 更新 head->next
            new_head = head; // 移動(dòng) new_head
            head = next2;
        }
        return new_head;
    }
};
int main(){ 
    ListNode a(11),b(22),c(33),d(44),e(55);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    Solution s; 
    ListNode *head = &a;
    // 逆序前，*head = &a
    printf("Before reverse:\n");
    while(head){
        printf("%d\n", head->val);
        head = head->next;
    }
    // 逆序后，*head = &e
    head = s.reverseList(&a);
    printf("After reverse:\n");
    while(head){
        printf("%d\n", head->val);
        head = head->next;
    }
    return 0;
}

鏈表部分逆序 (★★)

  • LeetCode 92. Reverse Linked List II.cpp
#include <stdio.h>

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL){ }
};
class Solution{
public:
    ListNode* reverseBetween(ListNode* head, int m, int n){
        int len = n - m + 1;
        ListNode *pre_head = NULL;
        // 循環(huán)后 => pre_head(1),head(2)
        while(head && --m){
            pre_head = head; 
            head = head->next;
        }
        ListNode *aft_head = head; // aft_head(2) 
        ListNode *new_head = NULL;
        // 逆序后 => 1(pre_head),4(new_head),3,2(aft_head),5(head)
        while(head && len){
            ListNode *next2 = head->next; 
            head->next = new_head; 
            new_head = head; 
            head = next2;
            len--;
        }
        // 更新 aft_head->next，即 2->5
        aft_head->next = head;
        // 更新 pre_head->next，即 1->4
        pre_head->next = new_head; 
        return pre_head;
    }
};
int main(){ 
    ListNode a(1),b(2),c(3),d(4),e(5);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    Solution s;
    ListNode *head = s.reverseBetween(&a, 2, 4);
    while(head){
        printf("%d\n", head->val);
        head = head->next;
    }
    return 0;
}

鏈表求交點(diǎn) (★)

  • 思路一，set 法求交集
  • LeetCode 160.Intersection of Two LinkedLists (solve1).cpp
#include <stdio.h>

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL){ }
};
// STL set 的使用 
#include <set>

class Solution{
public:
    // 求兩鏈表交點(diǎn) ( 鏈表 A頭指針，鏈表 B頭指針 )
    ListNode *Solve(ListNode *headA, ListNode *headB){
        // 查找集合 node_set
        std::set<ListNode*> node_set; 
        while(headA){
            // 各個(gè)節(jié)點(diǎn)都插入 node_set
            node_set.insert(headA);
            // 遍歷鏈表 A
            headA = headA->next;
        }
        while(headB){
            // 當(dāng)找到 node_set 的節(jié)點(diǎn)時(shí) 
            if (node_set.find(headB) != node_set.end()){
                return headB;
            }
            // 遍歷鏈表 B
            headB = headB->next;
        }
        // 若沒(méi)有交點(diǎn)，返回 NULL 
        return NULL;
    }
};

int main(){
    ListNode a1(1), a2(2);
    ListNode b1(3), b2(4), b3(5);
    ListNode c1(6), c2(7), c3(8);
    a1.next = &a2; a2.next = &c1;
    c1.next = &c2; c2.next = &c3;
    b1.next = &b2; b2.next = &b3; b3.next = &c1;
    // a1: 1，2，6，7，8 
    // b1: 3，4，5，6，7，8 
    Solution s;
    ListNode *result = s.Solve(&a1, &b1);
    printf("%d\n", result->val);
    return 0;
}
  • 思路二，空間復(fù)雜度法
  • LeetCode 160.Intersection of Two LinkedLists (solve2).cpp
#include <stdio.h>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
// 得到鏈表長(zhǎng)度 
int lenGet(ListNode *head){
    int len = 0;
    while(head){
        len++;
        head = head->next;
    }
    return len;
}

ListNode *forward_long_list(int long_len, int short_len, ListNode *head){
    // x 為鏈表長(zhǎng)度之差 
    int x = long_len - short_len;
    // 將長(zhǎng)鏈表頭向前移動(dòng) x 
    while(head && x){
        head = head->next;
        x--;
    }
    // 返回 head 指針 
    return head;
}

class Solution {
public:
    ListNode *Solve(ListNode *headA, ListNode *headB) {
        // A, B 鏈表長(zhǎng)度 
        int lenA = lenGet(headA);
        int lenB = lenGet(headB);   
        // 如果 A 更長(zhǎng)，移動(dòng) headA 
        if (lenA > lenB){
            headA = forward_long_list(lenA, lenB, headA);
        }
        // 如果 B 更長(zhǎng)，移動(dòng) headB 
        else{
            headB = forward_long_list(lenB, lenA, headB);
        }       
        // 當(dāng) headA == headB 時(shí)，就是交點(diǎn)  
        while(headA && headB){
            if (headA == headB){
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        // 若沒(méi)有交點(diǎn)，返回 NULL 
        return NULL;
    }
};

int main(){
    ListNode a1(1), a2(2);
    ListNode b1(3), b2(4), b3(5);
    ListNode c1(6), c2(7), c3(8);
    a1.next = &a2; a2.next = &c1;
    c1.next = &c2; c2.next = &c3;
    b1.next = &b2; b2.next = &b3; b3.next = &c1;
    // a1: 1，2，6，7，8 
    // b1: 3，4，5，6，7，8 
    Solution s;
    ListNode *result = s.Solve(&a1, &b1);
    printf("%d\n", result->val);
    return 0;
}

鏈表求環(huán) (★★)

  • 思路一，set 法求起始點(diǎn)
  • LeetCode 142. Linked List Cycle II (solve1).cpp
#include <stdio.h>
#include <set>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *Solve(ListNode *head) {
        // 設(shè)置 set 
        std::set <ListNode *> A;
        while(head){
            // 如果再次出現(xiàn)，且不是末尾 
            if (A.find(head) != A.end()){
                return head;
            }
            // 遍歷一遍后 set：123456 
            A.insert(head);
            head = head->next;
        }
        return NULL;
    }
};

int main(){
    ListNode a(1),b(2),c(3),d(4),e(5),f(6); 
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &c;
    Solution s;
    ListNode *node = s.Solve(&a);
    if (node){
        printf("有鏈表環(huán)，起始點(diǎn)：%d\n", node->val);
    }
    else{
        printf("NULL\n");
    }
    return 0;
}
  • 思路二，快慢指針?lè)?/li>
  • LeetCode 142. Linked List Cycle II (solve2).cpp
#include <stdio.h>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *Solve(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *meet = NULL;
        while(fast){
            slow = slow->next;
            fast = fast->next;
            fast = fast->next;
            // 若相遇，返回 meet = fast
            if (fast == slow){
                meet = fast;
                break;
            }
        }
        // 若不相遇，返回 NULL 
        if (meet == NULL){
            return NULL;
        }
        // 再移動(dòng) head、meet，找到環(huán)起點(diǎn) 
        while(head && meet){
            if (head == meet){
                return head;
            }
            head = head->next;
            meet = meet->next;
        }
        return NULL;
    }
};

int main(){
    ListNode a(1),b(2),c(3),d(4),e(5),f(6),g(7); 
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    g.next = &c;
    Solution s;
    ListNode *node = s.Solve(&a);
    if (node){
        printf("有鏈表環(huán)，起始點(diǎn)：%d\n", node->val);
    }
    else{
        printf("NULL\n");
    }
    return 0;
}

鏈表劃分 (★★)

  • 臨時(shí)結(jié)點(diǎn)頭法
  • LeetCode 86.Partition List.cpp
#include <stdio.h>
    
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* Solve(ListNode* head, int x) {
        ListNode less_head(0);  
        ListNode more_head(0); // 兩個(gè)臨時(shí)頭節(jié)點(diǎn) 
        ListNode *less = &less_head;
        ListNode *more = &more_head; // 兩個(gè)臨時(shí)指針 
        while(head){
            // 若小于 x，節(jié)點(diǎn)插入 less 后 
            if (head->val < x){
                less->next = head;
                less = head;
            }
            // 若大于 x，節(jié)點(diǎn)插入 more 后
            else {
                more->next = head;
                more = head;
            }
            head = head->next;
        }
        // 連接 less鏈表尾 more鏈表頭 
        less->next = more_head.next;
        more->next = NULL;
        return less_head.next;
    }
};

int main(){
    ListNode a(1),b(4),c(3),d(2),e(5),f(2);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;    
    Solution s;
    ListNode *head = s.Solve(&a, 3);    
    while(head){
        printf("%d\n", head->val);
        head = head->next;
    }
    return 0;
}

復(fù)雜鏈表的復(fù)制 (★★★)

  • LeetCode 138.Copy List with Random Pointer.cpp
#include <stdio.h>
        
struct RandomListNode {
    int label; // label 為節(jié)點(diǎn) 
    RandomListNode *next, *random; // random 為隨機(jī)指針 
    RandomListNode(int x) : label(x), next(NULL), random(NULL) { }
};

#include <map> // STL map 頭文件 
#include <vector>

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        std::map <RandomListNode *, int> node_map; // 地址到節(jié)點(diǎn)的 map 
        std::vector<RandomListNode *> node_vec; // 存儲(chǔ)節(jié)點(diǎn)的 vector
        RandomListNode *ptr = head;
        int i = 0;
        // 第一次遍歷 
        while (ptr){
            // 新鏈表的節(jié)點(diǎn)存儲(chǔ)到 node_vec
            node_vec.push_back(new RandomListNode(ptr->label));
            // 原鏈表地址到節(jié)點(diǎn)的 node_map
            node_map[ptr] = i; 
            ptr = ptr->next;
            i++;
        }
        node_vec.push_back(0);
        ptr = head;
        i = 0;
        // 第二次遍歷 
        while(ptr){
            // 連接新鏈表的 next 指針 
            node_vec[i]->next = node_vec[i+1]; 
            // 若 ptr->random 不為空
            if (ptr->random){
                // 根據(jù) node_map，原鏈表 random 指針指向 id 
                int id = node_map[ptr->random];
                // 連接新鏈表的 random 指針
                node_vec[i]->random = node_vec[id];
            }
            ptr = ptr->next;
            i++;
        }
        // 返回連接后的鏈表 
        return node_vec[0];
    }
};

int main(){
    RandomListNode a(1),b(2),c(3),d(4),e(5);
    a.next = &b;  b.next = &c;  c.next = &d;  d.next = &e;  
    // d->random 為空 
    a.random = &c;  b.random = &d;  c.random = &c;  e.random = &d;  
    Solution s;
    // 復(fù)制 random 隨機(jī)指向后的鏈表 
    RandomListNode *head = s.copyRandomList(&a);    
    while(head){
        printf("label = %d ", head->label);
        // 若 head->random 不為空 
        if (head->random){
            printf("random = %d\n", head->random->label);
        }
        // 若 head->random 為空 
        else{
            printf("random = NULL\n");
        }
        head = head->next;
    }
    return 0;
}

2 個(gè)排序鏈表歸并 (★)

  • LeetCode 21.Merge Two Sorted Lists.cpp
#include <stdio.h>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode temp_head(0); // 臨時(shí)節(jié)點(diǎn) temp_head 
        ListNode *pre = &temp_head; // pre 指針指向 temp_head 
        // 若兩節(jié)點(diǎn)都不為空 
        while (l1 && l2){
            // 將 pre 與較小的節(jié)點(diǎn)連接 
            if (l1->val < l2->val){
                pre->next = l1;
                l1 = l1->next;
            }
            else{
                pre->next = l2;
                l2 = l2->next;
            } 
            // pre 指向新節(jié)點(diǎn)  
            pre = pre->next;
        }
        // 如果 l1 有余，接到 pre 后 
        if (l1){
            pre->next = l1;
        }
        // 如果 l2 有余，接到 pre 后  
        if (l2){
            pre->next = l2;
        }
        return temp_head.next;
    }
};

int main(){
    ListNode a(1),b(4),c(6);
    ListNode d(0),e(5),f(7);
    a.next = &b;  b.next = &c;  
    d.next = &e;  e.next = &f;
    Solution s;
    // 合并排序兩個(gè)鏈表 
    ListNode *head = s.mergeTwoLists(&a, &d);
    while(head){
        printf("%d  ", head->val);
        head = head->next;
    }
    return 0;
}

K 個(gè)排序鏈表歸并 (★★★)

  • 思路一，暴力合并
  • 思路二，排序后相連
  • LeetCode 23.Merge k Sorted Lists(solve1).cpp
#include <stdio.h>
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

#include <vector>
#include <algorithm>
// 若 a 節(jié)點(diǎn)數(shù)值小于 b，則返回 true 
bool cmp(const ListNode *a, const ListNode *b){
    return a->val < b->val;
}
class Solution {
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        std::vector<ListNode *> node_vec;      
        // 遍歷所有鏈表
        for (int i = 0; i < lists.size(); i++){
            ListNode *head = lists[i];
            // 遍歷當(dāng)前鏈表所有節(jié)點(diǎn)，并存入 node_vec 
            while(head){
                node_vec.push_back(head);
                head = head->next;
            }
        }     
        // 根據(jù)節(jié)點(diǎn)數(shù)值進(jìn)行排序 
        std::sort(node_vec.begin(), node_vec.end(), cmp);
        // 連接所有排序后的節(jié)點(diǎn) 
        for (int i = 1; i < node_vec.size(); i++){
            node_vec[i-1]->next = node_vec[i];
        } 
        node_vec[node_vec.size()-1]->next = NULL;
        return node_vec[0];
    }
};
int main(){
    // 定義三個(gè)鏈表 
    ListNode a(1),b(4),c(6);
    ListNode d(0),e(5),f(7);
    ListNode g(2),h(3);
    a.next = &b;  b.next = &c;  
    d.next = &e;  e.next = &f;  
    g.next = &h;        
    // 將三個(gè)鏈表頭存入 lists 
    std::vector<ListNode *> lists; 
    lists.push_back(&a);
    lists.push_back(&d);
    lists.push_back(&g);
    Solution s; 
    ListNode *head1 = &a;
    // 輸出所有鏈表及歸并結(jié)果 
    printf("鏈表一 ："); 
    while(head1){
        printf("%d  ", head1->val);
        head1 = head1->next;
    }
    
    printf("\n鏈表二 ：");
    ListNode *head2 = &d;
    while(head2){
        printf("%d  ", head2->val);
        head2 = head2->next;
    }
    printf("\n鏈表三 ：");
    ListNode *head3 = &g;
    while(head3){
        printf("%d  ", head3->val);
        head3 = head3->next;
    }
    printf("\n歸并后 ：");
    ListNode *head = s.mergeKLists(lists);
    while(head){
        printf("%d  ", head->val);
        head = head->next;
    }
    return 0;
}
  • 思路三，分治后相連
  • LeetCode 23.Merge k Sorted Lists(solve2).cpp
#include <stdio.h>
struct ListNode {
    int val;
    ListNode *next;
    ListNode (int x) : val(x), next(NULL) {}
};

#include <vector>
class Solution {
public:
    // 兩個(gè)鏈表排序歸并 
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode temp_head(0);
        ListNode *pre = &temp_head;
        while (l1 && l2){
            if (l1->val < l2->val){
                pre->next = l1;
                l1 = l1->next;
            }
            else{
                pre->next = l2;
                l2 = l2->next;
            }
            pre = pre->next;
        }
        if (l1){
            pre->next = l1;
        }
        if (l2){
            pre->next = l2;
        }
        return temp_head.next;
    }   
    // 分治處理
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        // 如果一個(gè)鏈表，不做處理 
        if (lists.size() == 1){
            return lists[0];
        }
        // 如果兩個(gè)鏈表，排序歸并 
        if (lists.size() == 2){
            return mergeTwoLists(lists[0], lists[1]);
        } 
        // 拆分 lists 為 list1 、list2
        int mid = lists.size() / 2;
        std::vector<ListNode*> list1;
        std::vector<ListNode*> list2;
        for (int i = 0; i < mid; i++){
            list1.push_back(lists[i]);
        }
        for (int i = mid; i < lists.size(); i++){
            list2.push_back(lists[i]);
        }
        // list1 的一個(gè)鏈表，不做處理 
        ListNode *l1 = mergeKLists(list1);
        // list2 的兩個(gè)鏈表，排序歸并 
        ListNode *l2 = mergeKLists(list2);
        // list1、list2 兩鏈表排序歸并 
        return mergeTwoLists(l1, l2);
    }
};

int main(){
    // 定義三個(gè)鏈表 
    ListNode a(1),b(4),c(6);
    ListNode d(0),e(5),f(7);
    ListNode g(2),h(3);
    a.next = &b;  b.next = &c;  
    d.next = &e;  e.next = &f;  
    g.next = &h;        
    // 將三個(gè)鏈表頭存入 lists 
    std::vector<ListNode *> lists; 
    lists.push_back(&a);
    lists.push_back(&d);
    lists.push_back(&g);
    Solution s; 
    ListNode *head = s.mergeKLists(lists);
    // 輸出歸并結(jié)果 
    while(head){
        printf("%d  ", head->val);
        head = head->next;
    }
    return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容