世间所有的相遇，都是久别重逢

LeetCode题目总结-链表

发表于 分类于 ， 阅读次数： Disqus： Valine：
本文字数： 20k 阅读时长 ≈ 19 分钟

链表是一种利用不连续的内存块，通过在每块内存中存储下一块内存的指针而构造的线性存储结构，所以链表是线性表的一种形式。

链表问题是一种考察基本编码能力的问题，这类问题的特点是解法并不复杂，难点在于证明解法的正确性，以及如何编码。即，考察是否能编写出bug free的代码，少数会考察算法的数学证明问题。

很多链表的题目可以通过画图来辅助思考。

本文总结的链表题目主要包括以下部分：

链表的基础知识

数组和链表的对比可以看：数组和链表的区别。

链表类题目的常用技巧

  1. 使用dummy node：dummy node就是在链表的head前加一个节点指向head，即dummy->head，可以理解成一个虚拟节点。有了dummy node就使得操作head节点与操作其他节点没有区别。特别适合用在链表的head发生变化的情况下，譬如删除或者被修改等。
1
2
dummy = ListNode(0)
dummy.next = head
  1. 双指针法：对于寻找链表的某个特定位置，或者判断是否有环等问题时，可以用两个指针变量fast和slow，两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止。
1
2
slow = head
fast = head
  1. 交换节点的处理：如果需要交换两个节点的位置，对于这两个前驱节点，他们的next指针会受到影响，这两个节点本身也会受到影响，可以用以下步骤：
    • 先交换两个前驱节点的next指针的值
    • 再交换这两个节点的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
29
30
31
32
33
34
35
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Solution()代码
# ...
# ...


# 链表生成函数
def create_node_list(arr):
    head = ListNode(arr[0])
    cur = head
    for i in range(1, len(arr)):
        cur.next = ListNode(arr[i])
        cur = cur.next
    return head

# 链表打印函数
def print_node_list(head):
    while head:
        print(head.val, '->', end=' ')
        head = head.next
    print('NULL')


if __name__ == '__main__':
    arr = [4, 2, 1, 3]
    head = create_node_list(arr)
    print_node_list(head)

    x = Solution()
    print_node_list(x.reorderList(head))

链表的基本操作类题目

203-移除链表元素

题目描述

删除链表中等于给定值 val 的所有节点。

示例:

1
2
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

思路

这道题目可以用双指针解决：设置两个指针，一个指针（fast）遍历原链表，另一个指针（slow）指向一个新的链表，只要当前值不等于给定值val，就把当前值添加到slow指针后面。

不过这个方法用到了额外的空间，有没有办法在遍历过程中原地完成移除链表元素操作？

如果只用一个指针遍历链表，我们会发现，当我们遍历到一个节点时，其实就无法删除这个节点了。所以如果想要删除某个节点，就必须找到这个节点的前一个节点，把前一个节点的指针改变，即指向下下一个。这样即可完成原地移除链表元素。

下面是一个图解：

动画演示 203. 移除链表元素

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head

        p = dummy

        while p.next != None:
            # 当前值等于val，跳过，p指针不移动
            if p.next.val == val:
                p.next = p.next.next
            # 当前值不等于val，p指针后移
            else:
                p = p.next

        return dummy.next

237-删除链表中的节点

题目描述

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

示例 1:

  • 输入: head = [4,5,1,9], node = 5
  • 输出: [4,1,9]
  • 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2:

  • 输入: head = [4,5,1,9], node = 1
  • 输出: [4,5,9]
  • 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

说明:

  • 链表至少包含两个节点。
  • 链表中所有节点的值都是唯一的。
  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  • 不要从你的函数中返回任何结果。

思路

由于这道题目只输入了需要删除的节点node，因此无法获取删除节点node的前一个节点pre，从而也就无法将前一个节点pre指向删除节点的下一个节点next；既然无法通过修改指针完成，那么肯定要修改链表节点的值了，所以只要将删除节点node的值和指针都改为下一个节点next的值和指针即可。

Python实现

1
2
3
4
5
6
7
8
class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

21-合并两个有序链表

题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路

这里我们可以用到归并排序的思维。

我们维护一个 cur 指针，我们需要做的是调整它的 next 指针。如果 l1 当前位置的值小于等于 l2 ，我们就把 l1 的值接在 cur 节点的后面同时将 l1 指针往后移一个。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都把 cur 向后移一个元素。

在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        cur = dummy
        while l1 != None or l2 != None:
            # l1链表已经取完
            if l1 == None:
                cur.next = l2
                break
            # l2链表已经取完
            if l2 == None:
                cur.next = l1
                break

            if l1.val >= l2.val:
                cur.next = ListNode(l2.val)
                cur = cur.next
                l2 = l2.next
            else:
                cur.next = ListNode(l1.val)
                cur = cur.next
                l1 = l1.next
        return dummy.next

23-合并k个排序链表

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路

看到这道题目，我们首先会想到一个很简单粗暴的办法，就是两两合并这k个排序链表，一共需要k次合并操作。

  • 时间复杂度：O(kN)，其中 k 是链表的数目。

然后我们可以用分而治之的思想进行优化：

  1. 首先我们将 k 个链表配对并将同一对中的链表合并。两个链表的合并见第21题。
  2. 第一轮合并以后， k 个链表被合并成了 $\frac{k}{2}$ 个链表，平均长度为 $\frac{2N}{k}$ ，然后是 $\frac{k}{4}$ 个链表， $\frac{k}{8}$ 个链表等等。
  3. 重复这一过程，直到我们得到了最终的有序链表。

因此，我们在每一次配对合并的过程中都会遍历几乎全部 N 个节点，并重复这一过程 $\log_2K$ 次。

  • 时间复杂度： O(Nlogk) ，其中 k 是链表的数目。

合并K个排序链表

为什么这里分治的聚合次数是log2(K)次，而不是K-1次？

两个链表聚合确实发生了K-1次。但是注意，题解中把 K个链表两两聚合，生成K/2个链表的过程叫一次Merging。然后这样的Merging总共发生log(K)次。每一次Merging需要比较的次数是N。所以总的时间复杂度是O(N*log(K))。这才是两两聚合和逐一聚合的本质差别。

  • 逐一聚合的情况下，两个聚合的链表长度会发生偏斜，其中一个链表长度越来越长。考虑最坏情况K个链表每个仅包含一个元素（N为总元素数，这里N=K)，那么逐一聚合的总复杂度就是O(1+2+3+...N-1) = O(K*N).

  • 两两聚合的情况下，仍然考虑刚才的例子，

    • 第一轮K个链表，聚合完成后剩K/2个，发生的比较次数是 1 + 1 + 1 + ...+ 1 =1*K = N
    • 第二轮K/2个链表，聚合完成后剩K/4个，发生的比较次数是(最坏情况) 2+2+2+ ... + 2 = 2 * K/2 = N
    • 第三轮K/4个链表，聚合完成后剩K/8个，发生的比较次数 4 + 4 + 4 + .... + 4 = 4 * K/4 = N
    • …..
    • 最后一轮剩2个链表，比较次数 K/2 + K/2 = 2* K/2 = N
    • 总共有log(K)轮，总比较次数 N*log(K)

Python实现

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
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        k = len(lists)
        if k == 0:
            return None

        interval = 1
        # 两两合并
        while interval < k:
            for i in range(0,k,interval*2):
                # 最后落单的链表直接保留
                if i + interval < k:
                    lists[i] = self.mergeLists(lists[i],lists[i+interval])
            interval *= 2
        
        return lists[0]
        
    # 合并两个链表函数
    def mergeLists(self,l1,l2):
        dummy = ListNode(0)
        cur = dummy

        while l1 != None or l2 != None:
            if l1 == None:
                cur.next = l2
                break
            if l2 == None:
                cur.next = l1
                break

            if l1.val < l2.val:
                cur.next = ListNode(l1.val)
                cur = cur.next
                l1 = l1.next
            else:
                cur.next = ListNode(l2.val)
                cur = cur.next
                l2 = l2.next
        
        return dummy.next

86-分隔链表

题目描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

1
2
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

思路

如果不限制使用额外的空间的话，我们可以用两个链表，一个链表放小于x的节点，一个链表放大于等于x的节点，最后，拼接这两个链表。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        # 创建两个链表，分别保存小于x的数、大于等于x的数
        cur = head

        l1 = ListNode(0)
        l2 = ListNode(0)
        head1 = l1
        head2 = l2

        while cur != None:
            if cur.val < x:
                l1.next = ListNode(cur.val)
                l1 = l1.next
            else:
                l2.next = ListNode(cur.val)
                l2 = l2.next
            cur = cur.next
        
        # 两个链表拼接在一起
        l1.next = head2.next

        return head1.next

24-两两交换链表中的节点

题目描述

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

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

1
给定 1->2->3->4, 你应该返回 2->1->4->3.

思路

首先建立一个dummy为哑头节点，它的next指向head。为了保证节点不丢失，我一共设置了pre、a、b三个指针，然后更新指针，完成交换。这里迭代的终止条件是pre.next为空或pre.next.next节点为空（说明后面的节点不到两个，无需交换）。

下面是一个图解：

动画演示 24. 两两交换链表中的节点

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # 创建哑头节点
        dummy = ListNode(0)
        dummy.next = head

        pre = dummy
        a = dummy
        b = dummy

        while pre.next != None and pre.next.next != None:
            a = pre.next
            b = pre.next.next
            pre.next = b
            a.next = b.next
            b.next = a
            pre = pre.next.next
        
        return dummy.next

61-旋转链表

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

1
2
3
4
5
6
7
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

思路

链表中的点已经相连，一次旋转操作意味着：我们可以先将链表闭合成环，然后找到相应的位置断开这个环，最后确定新的链表头和链表尾。

具体步骤：

首先找到旧的尾部并将其与链表头相连（cur.next = head），整个链表闭合成环，同时计算出链表的长度n。然后找到新的尾部，第 n - k % n - 1 个节点 ，新的链表头是第 n - k % n 个节点。最后断开环 end.next = None，并返回新的链表头 new_head。

旋转链表

Python实现

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
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if head == None:
            return None
        if head.next == None:
            return head
        
        # 循环找到链表末尾
        n = 1
        cur = head
        while cur.next != None:
            cur = cur.next
            n += 1

        # 链表末尾连接到链表头
        cur.next = head

        # 循环找到链表第k个节点（拆分处）
        end = head
        for _ in range(n-k%n-1):
            end = end.next
        
        # 断开第k个节点
        new_head = end.next
        end.next = None

        return new_head

143-重排链表

题目描述

给定一个单链表 L：L0→L1→…→Ln-1→Ln，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

1
给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

1
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路

先将链表拆分成前后两半A和B。后一半B逆转成C。再将A和C交叉合并。

例如：1->2->3->4->5拆分成：A=1->2->3，B=4->5。然后把B逆转成C=5->4。最后A和C交叉合并成D=1->5->2->4->3。

Python实现

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
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if head == None:
            return None
        
        # 找到中间节点
        slow = head
        fast = head

        while fast.next != None and fast.next.next != None:
            slow = slow.next
            fast = fast.next.next
        
        # 从中间拆分成两个链表
        a = head
        b = slow.next
        slow.next = None

        # 反转链表B得到C
        pre = None
        cur = b
        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        c = pre

        # 交叉合并A、C得到D
        dummy = ListNode(0)
        d = dummy
        while a != None or c != None:
            if a != None:
                d.next = a
                d = d.next
                a = a.next
            if c != None:
                d.next = c
                d = d.next
                c = c.next
        
        return dummy.next

147-对链表进行插入排序

题目描述

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

  1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
  2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
  3. 重复直到所有输入数据插入完为止。

示例 1：

1
2
输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

1
2
输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路

按照插入排序的方法，只是这里每个数都是从链表的前面开始一个个比较。

Python实现

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
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        # 创建哑头节点（pre是一个新的链表）
        dummy = ListNode(0)
        pre = dummy

        cur = head

        while cur != None:
            # 保留cur.next的指针
            temp = cur.next

            # 链表中当前位置的数小于待插入的数，当前位置后移
            while pre.next != None and pre.next.val < cur.val:
                pre = pre.next
            
            # 已确定插入位置，完成插入
            cur.next = pre.next
            pre.next = cur
            
            # pre、cur改变（为下一次循环做准备）
            cur = temp
            pre = dummy

        return dummy.next

注意：结果链表pre是一个以dummy为首节点的新链表，跟原来的链表没关系。

148-排序链表

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

1
2
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

1
2
输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路

我这里用归并排序实现链表的排序。采用的是递归方法。

通过递归实现链表归并排序，有以下两个环节：

  1. 分割、排序环节：首先找到当前链表中点，并从中点将链表断开，以便在下次递归分割排序时，链表片段拥有正确边界：

    • 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
    • 找到中点 slow 后，执行 slow.next = None 将链表切断。
    • 递归分割时，输入当前链表左端点head和中心节点 slow 的下一个节点mid（因为链表是从 slow 切断的）。
    • 递归终止条件：当head.next == None时，说明只有一个节点了，直接返回此节点。

  2. 合并环节：我们将两个排序链表合并，转化为一个排序链表。这个过程跟第21题是一样的。

Sort List （归并排序链表）

Python实现

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
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # 递归终止条件
        if head == None:
            return None
        
        if head.next == None:
            return head

        # 双指针寻找链表中点
        slow = head
        fast = head

        while fast.next != None and fast.next.next != None:
            slow = slow.next
            fast = fast.next.next

        # 中点处切断链表，得到两个链表
        mid = slow.next
        slow.next = None

        # 递归
        l1 = self.sortList(head)
        l2 = self.sortList(mid)
        return self.merge(l1,l2)

    # 合并函数
    def merge(self, l1, l2):
        dummy = ListNode(0)
        cur = dummy
        while l1 != None or l2 != None:
            # l1链表已经取完
            if l1 == None:
                cur.next = l2
                break
            # l2链表已经取完
            if l2 == None:
                cur.next = l1
                break

            if l1.val >= l2.val:
                cur.next = ListNode(l2.val)
                cur = cur.next
                l2 = l2.next
            else:
                cur.next = ListNode(l1.val)
                cur = cur.next
                l1 = l1.next
        return dummy.next

注意：递归调用函数将带来O(logn)的空间复杂度，因此若希望达到O(1)空间复杂度，则不能使用递归。

反转类题目

单向链表的反转是一个非常常见的链表类面试题。

最简单易懂的办法就是使用一个数组来存储链表中的结点信息，比如结点的数据值等，之后根据题目要求对数组进行相关操作后，再重新把数组元素做为每一个结点连接成链表返回。但是这种办法空间复杂度达到了 O(n)，为了保证O(1)的空间复杂度，我们需要在原单链表的数据结构上，进行单链表反转，我们可以使用迭代或者递归完成。

  • 迭代：从前往后依次处理，直到循环到链尾
  • 递归：先一直迭代到链尾，也就是递归基判断的准则，然后再逐层返回处理到开头

下面是几个常见的题目：

206-反转链表

题目描述

反转一个单链表。

示例:

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

进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路

举例而言，现在我们有一个三个不同结点组成的链表 A → B → C，需要反转结点中的链接成为 A ← B ← C。

假设我们有两个指针，一个指向结点 A，一个指向结点 B。 分别记为 pre 和 cur。则可以用这两个指针简单地实现 A 和 B 之间的链接反转：

1
cur.next = pre

这样做唯一的问题是，没有办法继续下去，换而言之，这样做之后就无法再访问到结点 C。因此，我们需要引入第三个指针，用于帮助反转过程的进行。因此，我们不采用上面的反转方法，而是：

1
2
3
4
temp = cur.next
cur.next = pre
pre = cur
cur = temp

迭代地进行上述过程，即可完成问题的要求。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head

        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp

        return pre

这里要注意下，pre初始设置为None，保证了最后反转过来的链表最后指向的是None。

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

92-反转链表ii

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:1 ≤ m ≤ n ≤ 链表长度。

示例:

1
2
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路

我们需要两个指针 pre 和 cur。pre 指针初始化为 None，cur 指针初始化为链表的 head。然后我们同时向前推进 cur 指针，prev 指针跟随其后，直到 cur 指针到达从链表头起的第 m 个结点。这就是我们反转链表的起始位置。

这时候我们要引入两个额外指针，分别称为 tail 和 con。tail 指针指向从链表头起的第m个结点，此结点是反转后链表的尾部，故称为 tail。con 指针指向第 m 个结点的前一个结点，此结点是新链表的头部。tail 和 con 指针将在算法最后被调用，用于完成链表反转。

当 cur 指针抵达第 m 个结点后，迭代地反转链接，直到完成指向第 n 个结点的链接。此时，pre 指针会指向第 n 个结点。

这时候，我们使用 con 指针来连接 pre 指针，类似地，我们利用 tail 指针来连接 pre 指针之后的结点（第 n+1 个结点）。

下面是一个例子，给定一个链表 7 → 9 → 2 → 10 → 1 → 8 → 6，我们需要反转从第 3 个结点到第 6 个结点的子链表。具体过程如下：

从上图可以看到迭代法的前几步。第一步展示了两个指针的初始化，第三步显示链表到达了反转过程的初始位置。

上图详细显示了链接反转的过程以及反转两个结点的链接后如何向前移动。如下图所示，本步骤将执行多次。

如上图所示, 两个指针都已经到达最终位置。我们完成了子链表的反转工作。然而，还有一些链接需要调整。下图展示了利用 tail 和 con 指针完成链接调整的过程。

反转链表II

Python实现

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
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # 初始化pre、cur
        pre = None
        cur = head

        # cur 指针抵达第 m 个结点
        while m > 1:
            pre = cur
            cur = cur.next
            m -= 1
            n -= 1

        # 初始化con、tail
        con = pre
        tail = cur

        # 链表反转
        while n > 0:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
            n -= 1

        # con、tail链接调整
        if con:
            con.next = pre
        else:
            head = pre
        tail.next = cur

        return head

25-k个一组翻转链表

题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

1
2
3
4
5
给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路

具体步骤如下：

  1. 链表分区为已翻转部分+待翻转部分+未翻转部分。
  2. 每次翻转前，要确定翻转链表的范围，这个必须通过 k 次循环来确定，需记录翻转链表前驱（代码中的l_old，下图的pre）和后继（代码中的l_new，下图的next），方便翻转完成后把已翻转部分和未翻转部分连接起来。同时，k个一组的链表的头和尾我用start和end表示，start初始位于k个链表的第一个，而end初始位于其前驱。
  3. 经过k次循环，end 到达末尾，记录待翻转链表的后继 l_new = end.next，并把end断开，如下图第四行。
  4. 反转链表。
  5. 然后将三部分链表连接起来，然后重置 l_old（下图的pre） 和 end 指针，然后进入下一次循环。

图解k个一组翻转链表

Python实现

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
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:

        dummy = ListNode(0)
        dummy.next = head

        l_old = dummy
        end = dummy
        start = head

        while True:
            # k次循环，end到达一组的末尾
            for _ in range(k):
                end = end.next
                if end == None:
                    break

            # 链表到达末尾（剩余不够k个）
            if end == None:
                break

            # 分割开后面的链表
            l_new = end.next
            end.next = None
            # 反转这k个链表（返回的是反转后的头节点）
            temp = self.reverse(start)
            # 前面部分已反转完成的链表接上这个头节点
            l_old.next = temp
            # 更新这几个指针
            l_old = start
            end = start
            start.next = l_new
            start = start.next

        return dummy.next


    # 反转链表
    def reverse(self, head):
        dummy = ListNode(0)
        pre = dummy
        cur = head

        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp

        return pre

双指针问题

双指针算法，就是指的是在遍历的过程中，不是普通的使用单个指针进行循环访问，而是使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。

链表题目主要用的是相同方向的双指针，也就是快慢指针。快慢指针是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如 fast 每次增长两个，slow 每次增长一个。

下面是几个常见的题目：

19-删除链表的倒数第N个节点

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

1
2
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：给定的 n 保证是有效的。

进阶：你能尝试使用一趟扫描实现吗？

思路

首先我们将添加一个哑结点作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。

我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

删除链表的倒数第N个节点

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 设置哑头节点，简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。
        dummy = ListNode(0)
        dummy.next = head
        slow = dummy
        fast = dummy

        # 快指针先走n+1步
        for _ in range(n+1):
            fast = fast.next

        # 两个指针一起移动，直到快指针到达None
        while fast != None:
            slow = slow.next
            fast = fast.next

        # 删除慢指针指向的节点，也就是倒数第n个节点
        slow.next = slow.next.next

        return dummy.next

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

问题描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

  • 输入: 1->1->2
  • 输出: 1->2

示例 2:

  • 输入: 1->1->2->3->3
  • 输出: 1->2->3

思路

我首先想到可以把链表中的元素放入到一个集合set中，然后从头开始循环往下找，如果下一个结点的值在集合中出现过，那么更改当前结点的next指针，跳出下一个结点。

但是这样就没有用到输入的链表已排序这个条件。

其实我们可以将结点的值与它之后的结点进行比较来确定它是否为重复结点。如果它是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        
        current = head
        
        while current != None and current.next != None:
            if current.val == current.next.val:
                current.next = current.next.next
            else:
                current = current.next
        
        return head

82-删除排序链表中的重复元素ii

题目描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

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

示例 2:

1
2
输入: 1->1->1->2->3
输出: 2->3

思路

为了避免开头就出现重复数字，因此先加空头。

这里采用快慢指针，用快指针跳过那些有重复数组，慢指针负责和快指针拼接。

下面是一个图解：

来源：循环解法，简单高效，图解

Python实现

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
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head == None:
            return None

        # 创建空头
        dummy = ListNode(0)
        pre = dummy
        
        # 循环判断
        cur = head
        is_duplicate = False
        while cur != None and cur.next != None:
            if cur.val == cur.next.val:
                is_duplicate = True
                cur = cur.next
            else:
                if is_duplicate:
                    cur = cur.next
                    is_duplicate = False
                else:
                    # 这里要新建一个ListNode，而不是直接pre.next = cur
                    pre.next = ListNode(cur.val)
                    pre = pre.next
                    cur = cur.next
        
        # 链表最后一个数处理
        if is_duplicate == False:
            pre.next = ListNode(cur.val)
            pre = pre.next

        return dummy.next

141-环形链表

题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

思路

环形链表，即原本末尾的节点的 next 指针，指向了链表的任意一个节点，形成了一个闭环。在这种环形链表中，遍历时会停不下来，因为在环中会一直循环，这是它的特点。

我们设置两个指针：慢指针和快指针，慢指针每次移动一步，而快指针每次移动两步。我们可以把慢指针和快指针想象成两个在环形赛道上跑步的运动员（分别称之为慢跑者与快跑者）。而快跑者最终一定会追上慢跑者。

而如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        dummy = ListNode(0)
        dummy.next = head

        slow = dummy
        fast = dummy

        while fast.next != None and fast.next.next != None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True

        return False

142-环形链表ii

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

思路

首先我们设两指针 fast，slow 指向链表头部 head，fast 每轮走 2 步，slow 每轮走 1 步。

  • 如果fast指针走到链表末端，说明链表无环，直接返回 null。
  • 如果有环的话，两指针一定会相遇。

设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点，两指针分别走了 f，s 步。

当两指针在环中第一次相遇时，fast与slow走过的步数关系如下：

  • fast 走的步数是slow步数的 2 倍，即 f = 2s
  • fast 比 slow多走了 n 个环的长度，即 f = s + nb（双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走 环的长度的整数倍）

以上两式相减得：f = 2nb，s = nb，即fast和slow指针分别走了2n、n个环的周长

双指针第二次相遇：

我们会发现，所有走到链表入口节点时的步数是：a+nb（先走 a 步到入口节点，之后每绕 1 圈环都会再次到入口节点）。而目前，slow 指针走过的步数为 nb 步。因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口。但是我们不知道 a 的值，该怎么办？

我们依然可以使用双指针法。我们可以在链表头部head构建一个指针，此指针和slow一起向前走 a 步后，两者在入口节点重合。

环形链表 II（双指针法，清晰图解）

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        slow = dummy
        fast = dummy

        while True:
            # 链表无环
            if fast.next == None or fast.next.next == None:
                return None
            slow = slow.next
            fast = fast.next.next
            # 双指针第一次相遇
            if slow == fast:
                break

        # 构造第二次相遇
        fast = dummy
        while slow != fast:
            slow = slow.next
            fast = fast.next

        return slow

234-回文链表

题目描述

请判断一个链表是否为回文链表。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

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

思路

这道题目可以用快慢指针+反转链表解决。

  1. 使用快慢指针找到链表的中间位置，然后将链表分为两个部分
  2. 反转后半部分链表
  3. 逐一对比前后两部分链表

注意：如果链表长度是偶数的话，前半部分和后半部分长度是一样的。如果链表长度是奇数，那么前半部分的长度比后半部分长度多1个，所以最后迭代链表的时候，以后半部分为准就可以了，当链表总长为奇数时，前半部分的最后一个节点就不会被遍历到了。

Python实现

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
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head == None:
            return True

        # 快慢指针求得链表中点
        slow = head
        fast = head
        while fast.next != None and fast.next.next != None:
            slow = slow.next
            fast = fast.next.next
        # 中点处断开
        cur = slow.next
        slow.next = None

        # 反转后半个链表
        pre = None
        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp

        # 判断两个链表是否是回文链表
        l1 = head
        l2 = pre
        while l2 != None:
            if l2.val != l1.val:
                return False
            l2 = l2.next
            l1 = l1.next
        
        return True

328-奇偶链表

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

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

示例 2:

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

说明：应当保持奇数节点和偶数节点的相对顺序。链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

思路

我们可以利用两个指针完成分离：第一个指针odd连接奇数位结点，第二个指针even连接偶数位结点。分离结束后将odd段链表的尾指针指向even链表的head（即evenHead）。

双指针(c++)

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 特殊情况处理
        if head == None or head.next == None:
            return head

        # 奇偶指针初始化
        odd = head
        even = head.next
        evenHead = even

        # 奇偶指针分离
        while even != None and even.next != None:
            odd.next = odd.next.next
            odd = odd.next
            even.next = even.next.next
            even = even.next
        
        # 奇数链表的尾指针指向偶数链表的头指针
        odd.next = evenHead

        return head

数学问题

这部分包括一些非常典型的数学基本操作和链表基本操作题。

2-两数相加

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路

  1. 我们可以将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如 987 + 23 = 987 + 023 = 1010
  2. 每一位计算需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值
  3. 如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点 1

画解算法：2. 两数相加

Python实现

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
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 初始化结果链表
        cur = ListNode(0)
        head = cur
        
        carry = 0
        while l1 != None or l2 != None:
            # 如果一个链表较短则在前面补0
            if l1 == None:
                x1 = 0
            else:
                x1 = l1.val
                l1 = l1.next
            if l2 == None:
                x2 = 0
            else:
                x2 = l2.val
                l2 = l2.next

            # 每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值
            sums = (x1 + x2 + carry)%10
            carry = (x1 + x2 + carry)//10
            cur.next = ListNode(sums)
            cur = cur.next

        # 如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点 1
        if carry == 1:
            cur.next = ListNode(carry)

        return head.next

参考

推荐文章

----------- 本文结束啦感谢您阅读 -----------

赞赏一杯咖啡
disqus valine