grant's Blog

记录生活中的点点滴滴

LeetCode链表专题练习

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 7.9k 阅读时长 ≈ 7 分钟

专题学习路线参考： https://github.com/acm-clan/algorithm-stone。

本专题学习路线参考： https://github.com/acm-clan/algorithm-stone。

LeetCode题型总结： https://www.acwing.com/blog/content/4474/。

LeetCode题解参考：代码随想录和宫水三叶的刷题笔记。

本篇是LeetCode专题的第一篇：链表专题练习。

专题学习路线图：

https://raw.githubusercontent.com/acm-clan/algorithm-stone/main/images/leetcode_linked_list.svg。

T1—-707. 设计链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
 
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

1.设计单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class MyLinkedList {
public:
    int size;
    struct ListNode{
        int val;
        ListNode * next;

        ListNode(int _val): val(_val),next(nullptr){}
    }* head;

    MyLinkedList() {
        head = new ListNode(0);
        size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) return -1;

        auto p = head->next; // p赋值为首节点
        while (index --){ // inde = 0也能处理，如果--index就会死循环
            p = p->next;
        }
        return p->val;
    }
    
    void addAtHead(int val) {
        auto t = new ListNode(val);
        t->next = head->next;
        head->next = t;
        size ++;
    }
    
    void addAtTail(int val) {
        auto p = head;
        while (p->next) p = p->next;

        auto t = new ListNode(val);
        p->next = t;
        size ++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) return;
        else if (index <= 0) addAtHead(val);
        else{
            auto t = new ListNode(val);
            auto p = head;
            while (index --){
                p = p->next;
            }
            t->next = p->next;
            p->next = t;
        }
        size ++;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        auto p = head;
        while (index--){
            p = p->next;
        }
        auto t = p->next;
        p->next = p->next->next;
        delete t;
        size --;
    }
};

2.设计双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class MyLinkedList {
private:
    int size;
    struct ListNode{
      int val;
      ListNode *next,*prev;

      ListNode(int _val): val(_val),next(nullptr),prev(nullptr){}  
    };
    ListNode *head,*tail;

public:
    MyLinkedList() {
        size = 0;
        head = tail = new ListNode(0);
        head->next = tail,tail->prev = head;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) return -1;

        auto p = head->next;
        while (index --){
            p = p->next;
        }
        return p->val;
    }
    
    void addAtHead(int val) {
        auto t = new ListNode(val);
        t->next = head->next;
        t->prev = head;
        head->next->prev = t;
        head->next = t;

        size ++;
    }
    
    void addAtTail(int val) {
        auto t = new ListNode(val);
        t->next = tail;
        t->prev = tail->prev;
        tail->prev->next = t;
        tail->prev = t;

        size ++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) return;
        else if (index <= 0) addAtHead(val);
        else{
            auto p = head;
            auto t = new ListNode(val);
            while (index --){
                p = p->next;
            }
            t->next = p->next;
            t->prev = p;
            p->next->prev = t;
            p->next = t;
        }

        size ++;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;

        auto p = head;
        while (index --){
            p = p->next;
        }
        auto t = p->next;
        p->next = t->next;
        t->next->prev = p;
        delete t;

        size --;
    }
}

T2—-234. 回文链表

image-20220204204457634

提示：

链表中节点数目在范围[1, 10^5] 内

0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

本题的思路有很多种，常见的做法有：复制到数组然后双指针扫描判断回文，快慢指针，折半翻转链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// 题解一：
class Solution {
private:
    vector<int> a;
public:
    bool isPalindrome(ListNode* head) {
        for (ListNode* p = head;p ;p = p->next) a.push_back(p->val);

        bool flag = true;
        for (int l = 0,r = a.size()-1;l < r;l ++,r --){ // 注意不要写成l != r，偶数个节点时这是错的！
            if (a[l] != a[r]){ flag = false;break;}
        }

        if (flag) return true;
        else return false;
    }
};
----------------------------------------------
// 题解二：关于链表的翻转参考考研算法辅导课---重排链表，参考自y总视频
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n = 0;
        for (auto p = head ;p ;p = p->next) n ++; // 计算节点个数
        if (n <= 1) return true;

        auto a = head; // 编号0~n/2 - 1放在左侧链表
        for (int i = 0;i < n/2 - 1;i ++){
            a = a->next;
        }

        auto t = a->next;// 编号n/2 - 1作为右侧链表的最后一个节点
        auto b = t->next;
        a->next = t->next = nullptr;
        while (b){ // 翻转链表
            auto c = b->next;
            b->next = t;
            t = b,b = c;
        }

        auto x = t;auto y = head;
        bool flag = true; // 双指针判断回文
        for (int i = 0;i < n/2;i ++){
            if (x->val != y->val){
                flag = false;break;
            }
            x = x->next,y = y->next;
        }
		// 恢复链表，只考虑算法题可以不加，工程上最后恢复原状
        auto tail = t;
        auto p = tail->next;
        tail->next = nullptr;
        while (p){
            auto c = p->next;
            p->next = tail;
            tail = p,p = c;
        }
        a->next = tail;

        if (flag) return true;
        else return false;
    }
};
----------------------------------------------
// 题解三：快慢指针
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* prev = NULL;
        auto fast = head; // 快指针一次走两步，慢指针一次走一步
        auto slow = head; // 当快指针走到尾时慢指针走到中间位置（偶数个时偏右边）
        while (fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            ListNode *temp = slow->next;
            slow->next = prev; // 翻转前半链表
            prev = slow;
            slow = temp;
        }

        // 当有奇数个节点时，slow在中间位置，再向右走一步使得两边长度一样
        ListNode *prepre = slow; // 方便还原时把链表接上
        if (fast != NULL) slow = slow->next;

        auto p = prev;auto q = slow;
        // for (auto x = prev;x;x = x->next) cout << x->val << ' ';
        // for (auto x = slow;x;x = x->next) cout << x->val << ' ';
        bool flag = true;
        while (p != NULL){
            if (p->val != q->val){
                flag = false;break;
            }
            q = q->next;
            ListNode *temp = p->next;
            p->next = prepre; // 恢复链表
            prepre = p;
            p = temp;
        }

        // for (auto p = head;p;p = p->next) cout << p->val << ' ';
        return flag;
    }
};

T3—-206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

image-20220221174736792

简单题，遍历链表，每次改变一个指针的指向，然后移动一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode *p = head, *q = head->next;
        head->next = nullptr;
        while (q){
            auto temp = q->next;
            q->next = p;

            p = q;
            q = temp;
        }
        return p;
    }
};

T4—-24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

image-20220221182315464

读题：只有成对的节点才交换顺序，如果剩下一个不成对的节点则不交换。

参考题解。

题解一：递归写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        auto Next = head->next;
        head->next = swapPairs(Next->next);
        Next->next = head;
        return Next;
    }
};

题解二：迭代写法。

在head前面增加一个虚拟节点方便操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode *dummy = new ListNode(0); // 如果不加虚拟节点需要特判第一次交换
        dummy->next = head;
        auto p = dummy;
        while (p->next && p->next->next){
            auto node1 = p->next,node2 = p->next->next;
            p->next = node2;
            node1->next = node2->next;
            node2->next = node1;

            p = node1;
        }
        return dummy->next;
    }
};

T4—-24. 两两交换链表中的节点

坚持原创技术分享，您的支持将鼓励我继续创作！