美文网首页19-23年 学习笔记
【 数据结构 & 算法 】 —— 链表

【 数据结构 & 算法 】 —— 链表

作者: Du1in9 | 来源:发表于2020-09-29 18:45 被阅读0次

    < 思维导图 >

    预备知识：链表基础 (★)

    链表全部逆序 (★)

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

struct ListNode{ 
    int val; // 数据域
    ListNode *next; // 指针域       
    // 构造函数
    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; // 移动 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;
        // 循环后 => 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;
}

    链表求交点 (★)

    • 思路一，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:
    // 求两链表交点 ( 链表 A头指针，链表 B头指针 )
    ListNode *Solve(ListNode *headA, ListNode *headB){
        // 查找集合 node_set
        std::set<ListNode*> node_set; 
        while(headA){
            // 各个节点都插入 node_set
            node_set.insert(headA);
            // 遍历链表 A
            headA = headA->next;
        }
        while(headB){
            // 当找到 node_set 的节点时 
            if (node_set.find(headB) != node_set.end()){
                return headB;
            }
            // 遍历链表 B
            headB = headB->next;
        }
        // 若没有交点，返回 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;
}
    • 思路二，空间复杂度法
    • LeetCode 160.Intersection of Two LinkedLists (solve2).cpp
    #include <stdio.h>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
// 得到链表长度 
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 为链表长度之差 
    int x = long_len - short_len;
    // 将长链表头向前移动 x 
    while(head && x){
        head = head->next;
        x--;
    }
    // 返回 head 指针 
    return head;
}

class Solution {
public:
    ListNode *Solve(ListNode *headA, ListNode *headB) {
        // A, B 链表长度 
        int lenA = lenGet(headA);
        int lenB = lenGet(headB);   
        // 如果 A 更长，移动 headA 
        if (lenA > lenB){
            headA = forward_long_list(lenA, lenB, headA);
        }
        // 如果 B 更长，移动 headB 
        else{
            headB = forward_long_list(lenB, lenA, headB);
        }       
        // 当 headA == headB 时，就是交点  
        while(headA && headB){
            if (headA == headB){
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        // 若没有交点，返回 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;
}

    链表求环 (★★)

    • 思路一，set 法求起始点
    • 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) {
        // 设置 set 
        std::set <ListNode *> A;
        while(head){
            // 如果再次出现，且不是末尾 
            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("有链表环，起始点：%d\n", node->val);
    }
    else{
        printf("NULL\n");
    }
    return 0;
}
    • 思路二，快慢指针法
    • 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;
        }
        // 再移动 head、meet，找到环起点 
        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("有链表环，起始点：%d\n", node->val);
    }
    else{
        printf("NULL\n");
    }
    return 0;
}

    链表划分 (★★)

    • 临时结点头法
    • 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); // 两个临时头节点 
        ListNode *less = &less_head;
        ListNode *more = &more_head; // 两个临时指针 
        while(head){
            // 若小于 x，节点插入 less 后 
            if (head->val < x){
                less->next = head;
                less = head;
            }
            // 若大于 x，节点插入 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;
}

    复杂链表的复制 (★★★)

    • LeetCode 138.Copy List with Random Pointer.cpp
    #include <stdio.h>
        
struct RandomListNode {
    int label; // label 为节点 
    RandomListNode *next, *random; // random 为随机指针 
    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; // 地址到节点的 map 
        std::vector<RandomListNode *> node_vec; // 存储节点的 vector
        RandomListNode *ptr = head;
        int i = 0;
        // 第一次遍历 
        while (ptr){
            // 新链表的节点存储到 node_vec
            node_vec.push_back(new RandomListNode(ptr->label));
            // 原链表地址到节点的 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){
                // 根据 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;
    // 复制 random 随机指向后的链表 
    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 个排序链表归并 (★)

    • 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); // 临时节点 temp_head 
        ListNode *pre = &temp_head; // pre 指针指向 temp_head 
        // 若两节点都不为空 
        while (l1 && l2){
            // 将 pre 与较小的节点连接 
            if (l1->val < l2->val){
                pre->next = l1;
                l1 = l1->next;
            }
            else{
                pre->next = l2;
                l2 = l2->next;
            } 
            // pre 指向新节点  
            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;
    // 合并排序两个链表 
    ListNode *head = s.mergeTwoLists(&a, &d);
    while(head){
        printf("%d  ", head->val);
        head = head->next;
    }
    return 0;
}

    K 个排序链表归并 (★★★)

    • 思路一，暴力合并
    • 思路二，排序后相连
    • 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 节点数值小于 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];
            // 遍历当前链表所有节点，并存入 node_vec 
            while(head){
                node_vec.push_back(head);
                head = head->next;
            }
        }     
        // 根据节点数值进行排序 
        std::sort(node_vec.begin(), node_vec.end(), cmp);
        // 连接所有排序后的节点 
        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(){
    // 定义三个链表 
    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;        
    // 将三个链表头存入 lists 
    std::vector<ListNode *> lists; 
    lists.push_back(&a);
    lists.push_back(&d);
    lists.push_back(&g);
    Solution s; 
    ListNode *head1 = &a;
    // 输出所有链表及归并结果 
    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:
    // 两个链表排序归并 
    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) {
        // 如果一个链表，不做处理 
        if (lists.size() == 1){
            return lists[0];
        }
        // 如果两个链表，排序归并 
        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 的一个链表，不做处理 
        ListNode *l1 = mergeKLists(list1);
        // list2 的两个链表，排序归并 
        ListNode *l2 = mergeKLists(list2);
        // list1、list2 两链表排序归并 
        return mergeTwoLists(l1, l2);
    }
};

int main(){
    // 定义三个链表 
    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;        
    // 将三个链表头存入 lists 
    std::vector<ListNode *> lists; 
    lists.push_back(&a);
    lists.push_back(&d);
    lists.push_back(&g);
    Solution s; 
    ListNode *head = s.mergeKLists(lists);
    // 输出归并结果 
    while(head){
        printf("%d  ", head->val);
        head = head->next;
    }
    return 0;
}

    相关文章

      网友评论

        本文标题：【 数据结构 & 算法 】 —— 链表

        本文链接：https://www.haomeiwen.com/subject/rmpedktx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        19-23年 学习笔记

        关于我们|服务条款|联系我们|【 数据结构 & 算法 】 —— 链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！