七、链表问题（上）

160、相交链表（简单）

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例1：

示例2：

示例3：

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 10⁴
1 <= Node.val <= 10⁵

题目思路

对于这道题，是非常经典的链表类型的题目，要求获得两个链表交叉的位置（如果不交叉返回为空）。

需要注意的是，两个单链表的交叉，并不是像 “染色体” 那种X形式的交叉，因为一个单链表节点只能有一个后继（next），因此，只要交叉，就相当于二者汇融在了一起。

首先最直接的方法，是先获得两个链表的长度，然后让其中一个长度长的先走（len_a - len_b）的距离，最后，二者指针再一起走，就可以获得相交叉的节点了。

同时还有第二种不需要计算链表长度的方法：

创建指针 a 与 b ，分别指向headA与headB；
每步操作同时更新 a 与 b ：
- 如果指针 a 不为空，则将指针 a 移到下一个节点；如果指针 b 不为空，则将指针 b 移到下一个节点；
- 如果指针 a 为空，则将指针 a 移到链表 headB 的头节点；如果指针 b 为空，则将指针 b 移到链表 headA 的头节点；
当指针 a 和 b 指向同一个节点或者都为空时，返回它们指向的节点或者 None。

通过两个指针，第一轮让二者到达末尾的节点然后指向对方的头部，这样就相当于是抹除了距离差。
第二轮的行走，如果有交点，这二者一定会相交，否则二者会一同走到结尾的None。

算法代码

1、计算链表长度

class Solution:
    def getListLength(self, head):
        res = 0
        while head:
            res += 1
            head = head.next
        return res

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if headA is None or headB is None:
            return None

        len_a, len_b = self.getListLength(headA), self.getListLength(headB)

        if len_a >= len_b:
            gap = len_a - len_b
            while gap > 0:
                headA = headA.next
                gap -= 1
        else:
            gap = len_b - len_a
            while gap > 0:
                headB =headB.next
                gap -= 1

        while headA != headB:
            headA = headA.next
            headB = headB.next

        return headA

2、双指针法

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if headA is None or headB is None:
            return None

        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        
        return a

206、反转链表（简单）

题目描述

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

示例2：

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题目思路

对于这道题，也是链表问题中较为经典的类型——翻转。
题目的标准解法，就是通过定义一个prev节点来记录链表翻转后应当指向的节点：

记录当前节点head的下一个节点next（因为一旦翻转而不记录，原始next将会丢失）
head节点指向所记录的上一个节点prev；
prev节点指向当前的head节点，作为下一轮循环的上一个节点；
head节点指向第一步记录的next节点，作为下一轮循环的当前节点；

算法代码

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev_node = None
        
        while head:
            next_node = head.next
            head.next = prev_node
            prev_node = head
            head = next_node

        return prev_node

234、回文链表（简单）

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例1：

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

示例 2：

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

提示：

链表中节点数目在范围[1, 10⁵] 内
0 <= Node.val <= 9

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

题目思路

对于这道题，要求我们判断一个链表是否构成回文形式。
所谓回文，就是指1, 2, 2, 1这种形式，对于字符串或者数组而言，判断是否是回文相对简单，直接从两端向中间遍历即可。

但是在这道题中，所给定的数据结构为单链表，这就让直接比那
这里我们有两种思路：

1、辅助数组
直接定义一个数组，并在遍历链表的过程中将链其转化为数组、判断回文。
这种方法虽然简答，但需要额外开辟O(n)的空间。

2、快慢指针+翻转链表

利用快慢指针法，找到链表中间位置；
对后半段链表进行翻转，然后分别从原链表head与翻转后后半段链表头遍历、判断是否相等即可；

在这种方法中，不需要额外的列表进行存储，但有几点需要注意：

快慢指针法找中间位置时，链表节点个数偶数还是奇数需要单独判断：
- 对于奇数个节点的情况，slow还需再向后一位越过中位线；
后半段链表翻转后，注意前半段最后一个节点指向的还是后半段当前第一个节点，以此要以后半段作为遍历和判空条件；

算法代码

1、辅助数组

	class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if head.next is None:
            return True
        
        list_val = []
        while head:
            list_val.append(head.val)
            head = head.next

        n = len(list_val)
        for i in range(0, int(n/2)):
            if list_val[i] != list_val[n-1-i]:
                return False

        return True

2、快慢指针+翻转链表

	class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head

        # 使用快慢指针法找到链表中间位置
        # 注意链表节点个数偶数还是奇数需要单独判断
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 对于奇数个节点的情况，slow还需再向后一位越过中位线
        if fast:
            slow = slow.next

        # fast指向head，slow翻转，就可以通过直接比较的方法实现链表回文判断
        fast = head
        slow = self._reverse_list(slow)

        # 这里注意需要使用slow作为判断标准
        # 因为后半部分翻转不意味着前半部分末尾指向None
        while slow:
            if slow.val != fast.val:
                return False
            slow = slow.next
            fast = fast.next
        return True

    def _reverse_list(self, head):
        prev_node = None
        while head:
            next_node = head.next
            head.next = prev_node
            prev_node = head
            head = next_node
        return prev_node

141、环形链表（简单）

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

实例1：

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

实例2：

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

实例3：

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

提示：

链表中节点的数目范围是 [0, 104]
-10⁵ <= Node.val <= 10⁵
pos 为 -1 或者链表中的一个有效索引。

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

题目思路

对于这道题，是链表类问题中较为典型的一种，需要我们判断一个链表中是否有环。

对于这类判断链表是否有环问题，我们一般使用快慢指针法，即定义两个指针，一个为slow，一个为fast，从头开始对链表进行扫描：

指针slow每次走一步，指针fast每次走两步。
如果存在环，则这两个指针一定会相遇。
如果不存在环，则fast指针会最先到达NULL而退出。

为何说二者一定相遇？
因为fast会先进入环，在slow进入之后，如果把slow看做在前面，则fast在后面每次循环都会想slow靠近1，所以一定会相遇，而不会出现fast直接跳过slow的情况。

而另一类解法，则是直接对链表值做修改特殊值。
如果我们遍历了一个节点，那么我们就将其的值修改为特殊的——比如无穷大INF，这样我们一直遍历下去，如果再次找到了这样的值为INF的节点，那么我们就可以认为这个链表是有环的。

算法代码

1、快慢指针法

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

2、修改链表值

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        INF = float('inf')
        while head != None:
            if head.val != INF:
                head.val = INF
                head = head.next
            else:
                return True
        return False

142、环形链表 II（中等）

题目描述

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

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

示例 2：

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

示例3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 10⁴] 内
-10⁵ <= Node.val <= 10⁵
pos 的值为 -1 或者链表中的一个有效索引

进阶：

你是否可以使用 O(1) 空间解决此题？

题目思路

对于这道题，是在上一个判断链表是否有环的基础上更进一步、找到链表开始入环的第一个节点。

这里，我们同样使用快慢指针的方法，不过这里有一些比较巧妙的论证与计算。

首先，对于我们定义的快慢指针fast和slow，在本题的求解过程中，双指针会产生两次“相遇”。

第一次相遇：

设置指针fast与slow，指向链表头部；
每轮fast走2部，slow走一步；

如果链表存在环，那么双指针一定会相遇。因为每走 1 轮，fast 与 slow 的间距 +1，fast 一定会追上 slow 。

设两指针分别走了F和S的距离，因为fast走的步数是slow的两倍，因此我们有第一个关键公式：

F = 2 * S

其次，如下图所示，我们设定：

第一次相遇的点为Pos；
环的连接点（即题目希望求解的位置）为Join；
- 该位置设为环的起始位置，只要绕的圈数为整数圈，那么一定落在Join点；
头结点head到连接点Join的长度的为LenA;
连接点Join到第一次相遇点Pos的长度为x；
环的长度为R;

第一次相遇时，我们有：
slow走的长度为：S = LenA + x
fast走的长度为：F = LenA + n * R + x
- 这里n * R是因为在slow进入到环前，fast可能已经在环内走了n圈了；

根据第一个公式F = 2 * S，因此我们有：

LenA = n * R - x

由于此时slow从Join点已经走了x距离，那么只需要再走R - x的距离即可到达Join点。
因此，假如此时在第一次相遇后，我们让fast重新指向head，fast和slow同时每轮一步、走LenA的距离，那么此时slow行走后所在位置为：

x + LenA = x + n * R - x = n * R

而n * R恰好正是Join点所在的位置。

这个位置也恰好就是fast和slow第二次相遇的位置。

补充：
如果觉得n * R不好理解，将LenA设置较短、n变为0即可。

算法代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        has_cycle = False
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                has_cycle = True
                break

        if not has_cycle:
            return None

        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        
        return fast

21、合并两个有序列表（简单）

题目描述

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

示例 1：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

题目思路

对于这道题，整体较为简单，就是对两个链表同时进行遍历、不断修改next、最终达到重新组织排序的目的。

其中有几个注意点：

需要新创建一个pre_node用于记录链表开头部分；
定义start节点用于遍历、记录当前节点；
最后只要list1或list2还剩下元素，直接将其放在start后面即可；

算法代码

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        pre_head = ListNode(-1)
        start = pre_head
        while list1 and list2:
            if list1.val <= list2.val:
                start.next = list1
                list1 = list1.next
            else:
                start.next = list2
                list2 = list2.next
            start = start.next

        # 将剩下的链表直接放在结尾
        start.next = list1 if list1 else list2

        return pre_head.next