本文最后更新于：2023年8月23日 下午

学而时习，本文记录链表操作相关算法练习笔记。

反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        last_node = None
        current_node = pHead
        
        while current_node is not None:
            next_node = current_node.next
            current_node.next = last_node
            last_node = current_node
            current_node = next_node

        return last_node

复杂度

时间 空间
O(n) O(1)

解题备注

  • 维护当前节点，顺带考虑前后节点，会比较稳健
  • 设置虚拟前置节点，现场生成后置节点，更加鲁棒，甚至同时囊括了输入为None的情况
  • 需要注意返回前置节点作为新链表头

两个链表是否相交

这个问题有意思，也是力扣第 160 题「相交链表open in new window」函数签名如下：

1
ListNode getIntersectionNode(ListNode headA, ListNode headB);

给你输入两个链表的头结点 headA 和 headB，这两个链表可能存在相交。

如果相交，你的算法应该返回相交的那个节点；如果没相交，则返回 null。

比如题目给我们举的例子，如果输入的两个链表如下图：

那么我们的算法应该返回 c1 这个节点。

这个题直接的想法可能是用 HashSet 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间。

如果不用额外的空间，只使用两个指针，你如何做呢？

难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应：

如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。

所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？

这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        pa = headA
        pb = headB

        while pa != pb:
            if pa == None and pb == None:
                return None
            elif pa == None:
                pa = headB
                pb = pb.next
            elif pb == None:
                pb = headA
                pa = pa.next
            else:
                pb = pb.next
                pa = pa.next
        return pa

判断链表是否包含环

判断链表是否包含环属于经典问题了，解决方案也是用快慢指针：

每当慢指针 slow 前进一步，快指针 fast 就前进两步。

如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。

当然，这个问题还有进阶版，也是力扣第 142 题 环形链表 ：如果链表中含有环，如何计算这个环的起点？

可以看到，当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

为什么要这样呢？这里简单说一下其中的原理。

我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：

fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。

假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走k步可以转回到相遇点，那走 k - m 步肯定就走到环起点了：

所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。

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

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

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.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fake_head = ListNode(0)
        fake_head.next = head

        fast = fake_head
        slow = fake_head

        for _ in range(n):
            fast = fast.next
        while fast.next is not None:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return fake_head.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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        fake_head = ListNode(0)
        p = fake_head
        p1 = list1
        p2 = list2
        while p1 or p2:
            if p1 is None:
                p.next = p2
                p2 = p2.next
            elif p2 is None:
                p.next = p1
                p1 = p1.next
            else:
                if p1.val < p2.val:
                    p.next = p1
                    p1 = p1.next
                else:
                    p.next = p2
                    p2 = p2.next
            p = p.next
        return fake_head.next

分隔链表

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

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

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.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        large_head = ListNode(0)
        small_head = ListNode(0)
        large = large_head
        small = small_head
        p = head
        while p is not None:
            if p.val < x:
                small.next = p
                small = p
            else:
                large.next = p
                large = p
            
            p = p.next
        small.next = large_head.next
        large.next = None

        return small_head.next

链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = head
        slow = head
        while fast.next is not None:
            if fast.next is not None:
                fast = fast.next
            if fast.next is not None:
                fast = fast.next
            if slow.next is not None:
                slow = slow.next
        return slow

合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        import heapq

        res_fake_head = ListNode(0)
        p = res_fake_head
        heap = []
        for node in lists:
            if node:
                heapq.heappush(heap, (node.val, node))
                node = node.next
        while heap:
            _, cur_node = heapq.heappop(heap)
            p.next = cur_node
            p = cur_node
            if cur_node.next:
                heapq.heappush(heap, (cur_node.next.val, cur_node.next))

        return res_fake_head.next

206. 反转链表

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return head
        
        p = head
        q = head.next
        head.next = None
        while q is not None:
            r = q.next
            q.next = p
            p = q
            q = r
        return p

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 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
33
34
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == right:
            return head

        fake_head = ListNode(next=head)
        fake_head.next = head
        node = fake_head

        for step in range(left-1):
            node = node.next

        left_node = node
        node = node.next
        rev_left_node = node
        
        last_node = node
        cur_node = node.next

        for index in range(right - left):
            next_node = cur_node.next
            cur_node.next = last_node
            last_node = cur_node
            cur_node = next_node
        
        rev_left_node.next = cur_node
        left_node.next = last_node
        return fake_head.next

参考资料



文章链接：
https://www.zywvvd.com/notes/study/algorithm/list/about-list/

“觉得不错的话，给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

Algorithm
#Algorithm
算法学习笔记 —— 链表
https://www.zywvvd.com/notes/study/algorithm/list/about-list/
作者
Yiwei Zhang
发布于
2020年5月21日
许可协议