LeetCode刷题笔记 链表 链表的基础操作_leetcode链表的基本操作

链表简介

​ 链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针，因此很多链表问题可以用递归来处理。不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构储存长度。链表一般表示方法如下。

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

// 在节点 a->b 中插入 c 插入操作
ListNode *p = a;
c->next = b;
p->next = c;
p = c;
// 从链表 a->c->b 中删除节点 c
ListNode *p = c;
c = c->next;
a->next = c;
delete(p);
// 交换链表 a->c->b->d 中的 c 和 b 节点
a->next = b; // a 指向 b
c->next = b->next; // c 指向 d
b->next = c; // b 指向 c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

​ 由于在进行链表操作时，尤其是删除节点时，经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题：

• 一是尽量处理当前节点的下一个节点而非当前节点本身
• 二是建立一个虚拟节点 (dummy node)，使其指向当前链表的头节点，这样即使原链表所有节点全被删除，也会有一个 dummy 存在，返回 dummy->next 即可。

206 反转链表

翻转一个链表。

输入一个链表，输出该链表翻转后的结果。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解析：

​ 反转链表需要建立一个指向头节点的虚拟节点 prev，使用头节点的反转操作与其他节点保持一致。另外需要注意的是节点 next 指向改变的顺序，首先需要保存当前节点的 next 指向，然后修改其 next 指向为前一节点，最后移动指向前驱节点和当前节点的指针，完成一次反转操作。重复该操作，直至所有节点完成反转。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* next = head;
        while(head){
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

​ 本题也可以采用递归解决，终止条件为当前节点为空说明链表遍历完成。

class Solution {
public:
    ListNode* reverseListRec(ListNode* head, ListNode* prev){
        if(!head){
            return prev;
        }
        ListNode* next = head->next;
        head->next = prev;
        return reverseListRec(next,head);
    }

    ListNode* reverseList(ListNode* head) {
        return reverseListRec(head,nullptr);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

83 删除排序链表中的重复元素

给定一个按升序排列的链表，删除其中所有重复的元素

输入一个链表，输出该链表删除重复元素后的结果

输入：head = [1,1,2,3,3]
输出：[1,2,3]

解析：

​ 本题的本质上就是简单的链表删除节点操作，注意回收内存空间。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next){
            return head;
        }
        ListNode *cur = head;
        while(cur->next){
            if(cur->val == cur->next->val){
                ListNode *p = cur->next;
                cur->next = p->next;
                delete(p);
            }else{
                cur = cur->next;
            }
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

328 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。

输入一个链表，输出链表根据节点编号奇偶性重新组织后的结果

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

解析：

​ 本题并不复杂，只需要将奇偶编号的节点分开再合并即可。

​ 首先，将第一个节点作为奇数编号链表的头节点，第二个节点作为偶数编号链表的头节点

​ 然后，分别定义两个指针指向奇链表和偶链表的尾部，在原链表中：奇数编号节点的next就是偶数编号的节点，同样偶数编号节点的next就是奇数编号节点。

​ 所以一个奇偶链表的构造操作例子如下：

// 原链表
1  2  3  4
a->b->c->d
// 构造过程
ListNode *odd = a, *even = b; // 将 a 作为奇链表的头节点， b 作为偶链表的头节点，odd指向奇链表尾部，even指向偶链表尾部
odd->next = even->next; // a 指向 c
odd = odd->next; // odd 指向 c
even->next = odd->next; // b 指向 d
even = even->next; // even 指向 d
1
2
3
4
5
6
7
8
9

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || !head->next){
            return head;
        }
        ListNode *evenHead = head->next;
        ListNode *odd = head, *even = head->next;
        while(even && even->next){
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

24 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

输入一个链表，输出该链表交换后的结果。

输入：head = [1,2,3,4]
输出：[2,1,4,3]

解析：

​ 本题的关键就是不要把指针指向搞混，要注意两个相邻节点交换中指针的变换顺序

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *p = head, *s = nullptr;
        if(p && p->next){
            s = p->next;
            p->next = s->next;
            s->next = p;
            head = s;
            while(p->next&& p->next->next){
                s = p->next->next;
                p->next->next = s->next; 
                s->next = p->next;
                p->next = s;
                p = s->next;
            }
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

​ 采用递归更好理解本题，用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead->next。

令 head->next = swapPairs(newHead->next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead->next = head，即完成了所有节点的交换。

最后返回新的链表的头节点 newHead。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

21 合并两个有序链表

给定两个增序的链表，试将其合并成一个增序的链表。

输入两个链表，输出一个链表，表示两个链表合并的结果。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

解析：

​ 本题可以采用双指针求解，首先建立一个虚拟指针 dummy，其next指向合并后链表的头节点。用两个指针分别指向两个链表，逐个比较节点值大小插入合并链表。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1 || !l2){
            return l1?l1:l2;
        }
        ListNode dummy;
        ListNode* cur = &dummy;
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        while(p1&&p2){
            if(p1->val < p2->val){
                cur->next = p1;
                p1 = p1->next;
            }else{
                cur->next = p2;
                p2 = p2->next;
            }
            cur = cur->next;
        }
        cur->next = p1?p1:p2;
        return dummy.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

​ 本题也可以采用递归实现，将两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1 || !l2){
            return l1?l1:l2;
        }

        if(l1->val > l2->val){
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

​ 本题也可以采用STL中的容器适配器 priority_queue，把两个链表头节点存储在一个优先队列中，每次提取头节点值较小的那个节点，直到两个链表都被提取完为止。

​ 需要注意的是 priority_queue 默认的元素比较方法是less<T>，即默认为最大值元素在前面的最大堆，维持着递减关系。如果我们想要获取最小的节点值，则需要实现一个最小堆，因此比较函数应该维持递增关系。实现侧策略就是使用函数对象，自定义 priority_queue 的元素比较方法，在该函数对象中重载 operator() ，使用大于号而不是等减关系时的小于号进行比较。

struct myCompare{
    bool operator()(ListNode* a, ListNode* b){
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1 || !l2){
            return l1?l1:l2;
        }
        priority_queue<ListNode*, vector<ListNode*>, myCompare> pq;
        pq.push(l1);
        pq.push(l2);
        ListNode dummy;
        ListNode* cur = &dummy;
        while(!pq.empty()){
            cur->next = pq.top();
            pq.pop();
            cur = cur->next;
            if(cur->next){
                pq.push(cur->next);
            }
        }
        return dummy.next;
    }
};
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

23 合并 K 个升序链表

给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。

输入是一个一维数组，每个位置存储链表的头节点；输出是一条链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组：[1->4->5, 1->3->4, 2->6] 将它们合并到一个有序链表中得到：1->1->2->3->4->4->5->6

解析：

本题可以采用归并排序的思想，将链表两两合并。

根据分治策略，首先要将 k 个链表分割，使用递归的方法将链表分割为两两一组。然后将在同一个组的链表合并。

合并两个有序链表可以通过如下操作实现：

• 首先需要一个变量 head 来保存合并之后链表的头部，在整个链表合并完之后，返回 head 的下一位置即可。
• 需要一个指针 tail 来记录下一个插入位置的前一个位置，以及两个指针 aPtr 和 bPtr 来记录 a 和 b 未合并部分的第一位，即通过尾插法构建新链表
• 当 aPtr 和 bPtr 都不为空的时候，取 val 熟悉较小的合并；如果 aPtr 为空，则把整个 bPtr 以及后面的元素全部合并；bPtr 为空时同理。

class Solution {
public:
	// 合并两个升序链表
    ListNode* mergeTowList(ListNode* a, ListNode* b){
        if(!a || !b) return a?a:b;
        // 变量 head 来保存合并之后链表的头部
        ListNode head;
        ListNode* tail = &head;
        ListNode* aPtr = a;
        ListNode* bPtr = b;
        while(aPtr && bPtr){
            if(aPtr->val <= bPtr->val){
                tail->next = aPtr;
                aPtr = aPtr->next;
            }else{
                tail->next = bPtr;
                bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        // 循环结束 aPtr 和 bPtr 其中一个为空，直接将非空的添加到链表
        tail->next = aPtr?aPtr:bPtr;
        return head.next;
    }

	// 划分链表列表
    ListNode* merge(vector<ListNode*>& lists, int lsh, int rsh){
        if(lsh == rsh){
            return lists[lsh];
        }
        if(lsh > rsh){
            return nullptr;
        }
        int mid = (lsh + rsh) >> 1;
        return mergeTowList(merge(lists,lsh,mid),merge(lists,mid+1,rsh));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists,0,lists.size()-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

148 排序链表

给定一个链表，请将其按 升序 排列并返回 排序后的链表

输入一个链表，输出按升序排序的链表

输入：head = [4,2,1,3]
输出：[1,2,3,4]

解析：

​ 本题可以采用归并排序的思想解决。

​ 分治策略：首先使用快慢指针找链表中点的方法找到链表中点，然后以此将链表分割为两个部分，然后再进行递归的划分链表，直到不可划分。在寻找中点需要注意的是不能直接以 nullptr 判断快指针是否达到终点，而是要将其与链表尾节点 tail 进行比较。

​ 分割完成之后，使用合并两个链表的方法，将链表按照升序合并，最终形成完整的升序链表。

class Solution {
public:
	// 将两个链表按照升序合并
    ListNode* mergeTwoList(ListNode* l1, ListNode* l2){
        if(!l1 || !l2) return l1?l1:l2;
        ListNode head;
        ListNode *tail = &head;
        ListNode *p1 = l1, *p2 = l2;
        while(p1 && p2){
            if(p1->val < p2->val){
                tail->next = p1;
                p1 = p1->next;
            }else{
                tail->next = p2;
                p2 = p2->next;
            }
            tail = tail->next;
        }
        tail->next = p1?p1:p2;
        return head.next;
    }

    ListNode* mergeSort(ListNode* head, ListNode* tail){
        if(!head) return head;
        if(head->next == tail){
            head->next = nullptr;
            return head;
        }
        // 寻找链表中点
        ListNode *fast = head, *slow=head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) {
                fast = fast->next;
            }
        }
        ListNode* mid = slow;
        // 根据链表中点递归分割，并合并结果
        return mergeTwoList(mergeSort(head,mid),mergeSort(mid,tail));
    }

    ListNode* sortList(ListNode* head) {
        return mergeSort(head,nullptr);
    }
};
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

参考资料

LeetCode 101：和你一起轻松刷题(C++) 第 13 章 指针三剑客之链表