算法之美-链表问题

Algorithms To Live By Comments

17.从尾到头打印链表

https://www.acwing.com/problem/content/18/

题目

1
2
3
4
5
6
7
8
9
10
输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

数据范围
0≤ 链表长度 ≤1000。

样例
输入：[2, 3, 5]
返回：[5, 3, 2]

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> result;
        while(head) {
            result.push_back(head->val);
            head = head->next;
        }
        return vector<int>(result.rbegin(), result.rend());
    }
};

相关知识 - 反向迭代器

image-20220110233358784

begin() 返回一个迭代器，它指向容器的第一个元素

end() 返回一个迭代器，它指向容器的最后一个元素的下一个位置

rbegin() 返回一个逆序迭代器，它指向容器的最后一个元素

rend() 返回一个逆序迭代器，它指向容器的第一个元素前面的位置

应用场景：

1
2
3
4
//sorts v in "normal" order
sort(v.begin(), v.end());
//sorts in reverse
sort(v.rbegin(), v.rend());

28.O(1)删除链表结点

题目

https://www.acwing.com/problem/content/85/

1
2
3
4
5
6
7
8
9
10
11
12
给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。

假设链表一定存在，并且该节点一定不是尾节点。

数据范围
链表长度 [1,500]。

样例
输入：链表 1->4->6->8
      删掉节点：第2个节点即6（头节点为第0个节点）

输出：新链表 1->4->8

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* nxt = node->next;
        node->val = nxt->val;
        node->next = nxt->next;
        
        delete nxt;
    }
};

相关知识

1
2
//1. auto: 在声明变量的时候可根据变量初始值的数据类型自动为该变量选择与之匹配的数据类型
//2. delete TODO

29.删除链表重复节点

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。

样例1
输入：1->2->3->3->4->4->5

输出：1->2->5
样例2
输入：1->1->1->2->3

输出：2->3

注意重复的节点也不保留

解答

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode * dummy = new ListNode(-1);	//定义一个头指针(防止head为空)
        dummy->next = head;
        ListNode * pre = dummy;	//双指针前指针
        while(pre->next) {	
            ListNode * nxt = pre->next;	//双指针尾指针
          	//一直循环，直到头指针与尾指针值不一致
          	//注意这里pre是从dummy开头的，而这题是要删除所有重复的节点，所以有时候pre—>next需要一起删除
          	//所以这里每次都是比较 pre->next 与 nxt
            while(nxt && pre->next->val == nxt->val) nxt = nxt->next;	
            
       			//经过上述流转出现 pre->next->val != nxt->val
          	//1. 如果两者相邻，那么pre向后移动一个节点
          	//2. 如果两者不相邻，那么pre与nxt之间都是重复节点
            if (pre->next->next == nxt) pre = pre->next;
            else pre->next = nxt;
        }
        return dummy->next;
    }
};

重点：是每次使用 pre->next 与 nxt进行比较，那样即使删除也是删除pre->next 与 nxt之间的结点

33.链表中倒数第N个节点

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
输入一个链表，输出该链表中倒数第 k 个结点。

注意：

k >= 1;
如果 k 大于链表长度，则返回 NULL;
数据范围
链表长度 [0,30]。

样例
输入：链表：1->2->3->4->5 ，k=2

输出：4

解答

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(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        //使用快慢指针
        ListNode *fast = pListHead;
        ListNode *slow = pListHead;
        //快指针先走k步，如果fast为空或者为空都没有走到k个，说明链表数目小于k
        for (int i = 0; i < k; i++) {
            if (fast) fast = fast->next;
            //这里k-1 是因为 i = 0 即为第一个节点 fast 需要走 i =  k - 1 步
            if (!fast && i < k - 1) return NULL;
        }
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

重点：快慢指针

34.链表中环的入口节点

题目

https://www.acwing.com/problem/content/86/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

数据范围
节点 val 值取值范围 [1,1000]。
链表长度 [0,500]。

样例如下图

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

QQ图片20180531162503.png

证明：

如上图所示，a 是起点，b 是环的入口，c 是两个指针的第一次相遇点，ab 距离 x，bc 距离是 y

存在快慢指针 first 与 second，其中second的速度是first的2倍

想法1：

当 first 走到 b 时， second 已经从 b 开始在环上走了 x 步，可能多余n圈，距离 b 还差 y 步

所以 second 走的路程 2x + y = x + n 圈 ==> x + y = n 圈，那么从 c 走 x 步 也能到达b

想法2：

用 z 表示从 c 点顺时针走到 b 的距离。则第一次相遇时 second 所走的距离是 x+(y+z)∗n+y，其中n表示圈数，所以

1
2
x+(y+z)∗n+y = 2(x+y) //second是 first路程的两倍
x = (n-1) * (y+z) + z

所以其实 x == z ，相遇之后节点距离入环扣与链表头到入环扣距离相等

解答

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
       if (!head || !head->next) return NULL;	//初始节点判断
       
       //快慢指针
       ListNode * first = head;
       ListNode * second = head;
       while (first && second){  //外循环防止节点为空，找到第一个相遇的地方
           first = first->next;
           second = second->next;
           if(second) second = second->next;
           else return NULL;
           
           if (first == second) { //当相遇则再次相遇说走的路程就是换入口处
               first = head;
               while (first != second) {
                   first = first->next;
                   second = second->next;
               }
               return first;
           }
       }
       return NULL;
    }
};

重点是：从第一次相遇的地方走x步就能到达入环扣

35.反转链表

题目

1
2
3
4
5
6
7
8
9
10
11
12
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

请同时实现迭代版本和递归版本。
数据范围
链表长度 [0,30]。

样例
输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

解答

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * second = head;     
        ListNode * first = nullptr;	//头部空指针
        while(second) {
            ListNode * pre = second->next;
            second->next = first;
            first = second;
            second = pre;
        }
        return first;
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next ) return head;
        
        //1 - 2 - 3 - 4
        ListNode *tail = reverseList(head->next);   //反转head->next 链表, 原链表的尾节点tail
        //为什么不用记录前一个节点进行转换，
        //因为 递归中 head->next 已经经过了反转，后面只需要反转 head 与 head->next的关系就可以了
        head->next->next = head;    //将 这里直接使用 head->next->next 不用再声明变量
        head->next = nullptr;       // nullptr <- 1 <- 2
        return tail;    //其实这里一直返回的是原链表的尾节点
    }
};

36.合并两个排序的链表

题目

https://www.acwing.com/problem/content/34/

1
2
3
4
5
6
7
8
9
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围
链表长度 [0,500]。

样例
输入：1->3->5 , 2->4->5

输出：1->2->3->4->5->5

解答

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(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {        
        ListNode * dummy = new ListNode(-1);	//新建头部的保护结点dumm
        ListNode * cur = dummy;		//当前指针
        
        while(l1 && l2) {
            if(l1->val > l2->val) {
                cur->next = l2;
                l2 = l2->next;
            }else{
                cur->next = l1;
                l1 = l1->next;
            }
            cur = cur->next;
        }
      	//二元判断，防止两个链表数目不一致
        cur->next = (l1 != nullptr ? l1 : l2);
        return dummy->next;
    }
};

两个链表各遍历一次，所以时间复杂度为O(n)

48. 复杂链表的复刻

题目

https://www.acwing.com/problem/content/89/

1
2
3
4
5
6
7
8
9
请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

函数结束后原链表要与输入时保持一致。
数据范围
链表长度 [0,500]。

解答

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
/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        
        //开始遍历添加cur的复制点np
        ListNode * p = head;
        while(p) {
            //1 - 2 --> 1 - 1 - 2  复制节点并添加到节点后面
            auto * np = new ListNode(p->val);
            auto * nxt = p->next;
            p->next = np;
            np->next = nxt;
            p = nxt;
        }
        
        //如果存在 cur 有 random 则 p->next 是被复制的节点
        p = head;
        while (p) {
            if(p->random) //p 是旧节点,则 p->next 是新节点
                p->next->random = p->random->next; //这里也是随机指定，和原来的不一定相等
            p = p->next->next;
        }
        
        ListNode * dummy = new ListNode(-1); //保护头节点
        ListNode * cur = dummy;
        p = head;
        while(p) {
          	//1 - 1 - 2 - 2 - 3 - 3
            cur->next = p->next;	//新链表
            cur = cur->next;
            p->next = p->next->next; //恢复旧指针
            p = p->next;
        }
        return dummy->next;
    }
};

重点是：p->next->random = p->random->next; //如果有random，则它是原节点。将新节点指一个random

49.二叉搜索树与双向链表

https://www.acwing.com/problem/content/87/

题目

QQ截图20181202052830.png

1
2
3
4
5
6
7
8
9
10
11
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

注意：

需要返回双向链表最左侧的节点。
例如，输入上图中左边的二叉搜索树，则输出右边的排序双向链表。

数据范围
树中节点数量 [0,500]。

解答

在中序递归遍历的基础，用一个pre指针保存中序遍历的前一个结点。遍历顺序就是双线链表的建立顺序；
每一个结点访问时它的左子树肯定被访问过了，所以放心大胆的改它的left指针，不怕树断掉；
同理，pre指向的结点保存的数肯定小于当前结点，所以其左右子树肯定都访问过了，所以其right指针也可以直接改。

最后需要一直向左找到双向链表的头结点。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    TreeNode * pre = NULL;  //pre记录当前节点指针
    
    TreeNode* convert(TreeNode* root) {
       dfs(root);
       while(root && root->left) root = root->left; //遍历找到第一个节点
       return root;
    }
    
    //深度优先遍历
    void dfs(TreeNode* root) {
        if(!root) return;
        
        dfs(root->left);
        root->left = pre;	//左节点就是前节点
        if(pre) pre->right = root;	//前节点的后继节点就是自己
        pre = root; 
        
        dfs(root->right);
    }
};

重点是：利用深度优先遍历 + pre节点记录

66. 两个链表的第一个公共结点

题目

https://www.acwing.com/problem/content/62/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。

数据范围
链表长度 [1,2000]。

样例
给出两个链表如下所示：
A：        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

不要用两层循环暴力破解！！！

解答

不同部分为a和b，公共部分为c；a + c + b = b + c + a;让两个一起走，a走到头就转向b， b走到头转向a，则在公共部分相遇

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        ListNode * A = headA;
        ListNode * B = headB;
        while(A != B) {
            //A遍历完开始走到B
            if(A) A = A->next;
            else A = headB;
            
            //B遍历完开始走到A
            if(B) B = B->next;
            else B = headA;
        }
        return A;
    }
};

826. 单链表

题目

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
实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；
删除第 k 个插入的数后面的数；
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式
第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

H x，表示向链表头插入一个数 x。
D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式
共一行，将整个链表从头到尾输出。

数据范围
1≤M≤100000
所有操作保证合法。

输入样例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例：
6 4 6 5

解答

静态链表

1451. 单链表快速排序

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个单链表，请使用快速排序算法对其排序。

要求：期望平均时间复杂度为 O(nlogn)，期望额外空间复杂度为 O(logn)。

思考题： 如果只能改变链表结构，不能修改每个节点的val值该如何做呢？

数据范围
链表中的所有数大小均在 int 范围内，链表长度在 [0,10000]。

输入样例：
[5, 3, 2]
输出样例：
[2, 3, 5]

解答

首先复习以下快速排序

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
//用于默写test中国暖的算法
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 1;
int nums[N];    //用于存储数据
int n;

void quick_sort(int nums[], int l, int r)
{
    if(l >= r) return;

    int mid = nums[l + r >> 1];
    int i = l - 1;
    int j = r + 1;
    while(i < j)
    {
        do i++; while (nums[i] < mid);
        do j--; while (nums[j] > mid);
        if (i < j) swap(nums[i], nums[j]);	//表示num[i] 在左边但是数据却比 num[j] 大
    }
    quick_sort(nums, l, i);
    quick_sort(nums, i + 1, r);

    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &nums[i]);
    quick_sort(nums, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", nums[i]);
    return 0;
}

则链表排序为

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 1;
int n;

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

void quickSort(ListNode *head, ListNode *tail)
{
    if (head != tail)
    {
        int key = head->val;
        ListNode *p = head, *q = p->next;
        while (q != tail)
        {
            if (q->val < key)
            {
                p = p->next;
                swap(p->val, q->val);
            }
            q = q->next;
        }
        if (p != head)
            swap(head->val, p->val);

        quickSort(head, p);
        quickSort(p->next, tail);
    }
}

ListNode *quickSortList(ListNode *head)
{
    if (!head)
        return head;
    quickSort(head, NULL);
    return head;
}

int main()
{
    ListNode * head = new ListNode(-1);
    ListNode * cur = head;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);

        ListNode * node = new ListNode(val);
        cur->next = node;
        cur = cur->next;
    }

    ListNode * result = quickSortList(head->next);
    while (result)
    {
        printf("%d", result->val);
        result = result->next;
    }
    
    return 0;
}

1560. 反转链表

题目

https://www.acwing.com/problem/content/1562/

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
给定一个常数 K 和一个单链表 L，请你在单链表上每 K 个元素做一次反转，并输出反转完成后的链表。

如果链表最后一部分不足 K 个元素，则最后一部分不翻转。

例如，假设 L 为 1→2→3→4→5→6，如果 K=3，则你应该输出 3→2→1→6→5→4；如果 K=4，则你应该输出 4→3→2→1→5→6。

### 补充
1、本题中可能包含不在链表中的节点，这些节点无需考虑。

### 输入格式
第一行包含头节点地址，总节点数量 N 以及常数 K。

节点地址用一个 5 位非负整数表示（可能有前导 0），NULL 用 −1 表示。

接下来 N 行，每行描述一个节点的信息，格式如下：
`Address Data Next`
其中 Address 是节点地址，Data 是一个整数，Next 是下一个节点的地址。

### 输出格式
将重新排好序的链表，从头节点点开始，依次输出每个节点的信息，格式与输入相同。

### 数据范围
1≤N≤105,
1≤K≤N

### 输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

### 输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

参考链接

  1. https://www.acwing.com/problem/