Leetcode刷题笔记4：链表基础2

导语

leetcode刷题笔记记录，本篇博客记录链表基础2部分的题目，主要题目包括：

24 两两交换链表中的节点
19 删除链表的倒数第N个节点
160 链表相交
142 环形链表II

链表的定义

Python中，对于一个链表的节点定义非常简单，只要包含数据和指针字段即可，如：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

解法

这道题目还是可以通过添加一个虚拟头结点的方式完成，在head前面新建一个dummpy_head节点指向head，之后，使用三个指针，分别标记前一个节点、当前节点和后一个节点，然后按下图方式更新前一个节点、当前节点的next指针即可。

这里以两个节点为一组，分别进行处理，最后剩下一个或者None时，停止操作。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummpy_head = ListNode(0, head)
        current = dummpy_head
        while current.next is not None and current.next.next is not None:
            temp = current.next
            temp1 = current.next.next.next
            current.next = current.next.next
            current.next.next = temp
            temp.next = temp1
            current = current.next.next
        
        return dummpy_head.next

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

题目描述

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

示例 1：

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

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

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

解法

这个题目仍可以使用双指针的思路来解决，通过定义一个快指针fast和慢指针slow，其中fast可以先走n步，然后，fast和slow同时向后移动，这样等fast走到链表尾部None时，slow就刚好在倒数第n个位置。进行一步删除的操作即可，值得注意的是，要删除这个节点，必须找到这个节点的前一个节点，才能进行删除。

主要代码如下：

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_head = ListNode(0, head)
        slow = dummy_head
        fast = dummy_head
        for i in range(n):
            fast = fast.next
        while fast.next is not None:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy_head.next

由于原题目并没有给我们链表节点的定义，所以这里需要自己定义一下链表节点ListNode。这里的几个易错点为：

进行查询、增删时，一定要先判断给定的索引范围；
增删完成后，注意及时更新size

Leetcode 160 链表相交

题目描述

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

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

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

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

示例 1：

输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出： Intersected at '8'
解释： 相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶： 你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

解法

本题目同样可以通过两个指针curA，curB来解决。首先求出两个链表的长度及其长度的差值，然后让curA移动到，和curB （假设短的那个是B）末尾对齐的位置，此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。

完整的代码如下：

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        curA, curB = headA, headB
        tempA, tempB = curA, curB
        sizeA, sizeB = 0, 0
        while tempA is not None:
            sizeA += 1
            tempA = tempA.next
        while tempB is not None:
            sizeB += 1
            tempB = tempB.next
        if sizeA >= sizeB:
            offset = sizeA - sizeB
            for i in range(offset):
                curA = curA.next
            length = sizeB
        else:
            offset = sizeB - sizeA
            for i in range(offset):
                curB = curB.next
            length = sizeA
        while curA != curB and length != 0:
            curA = curA.next
            curB = curB.next
            length -= 1
        if length == 0:
            return None
        else:
            return curA

Leetcode 142 环形链表II

题目描述

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

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

不允许修改 链表。

示例 1：

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

提示：

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

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

解法

这个题目有两个考察点：

如何判断是否有环？
如何求出环的入口。

对于第一个问题，一般使用双指针的思路，即定义一对快慢指针，快指针每次走2步，慢指针每次走一步，看看二者是否相遇即可。

对于第二个问题，则需要一定的数学推导，如图所示，假设环的入口为x，假设两个指针在环的一点y相遇，剩余环的长度为z，那么可以推导得到，

$x = (n - 1) (y + z) + z$

这里(y+z)实际就是一个环的长度，所以可以得到以下结论：

当一个节点p1从head出发，另一个节点p2从相遇点出发，他们一定会在环的入口处x相遇。

通过以上推导，可以写出下面的代码：

首先得到相遇点的位置；
初始化另一个指针从头出发，可以求得环的入口x位置。

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head, head
        while True:
            if fast is None or fast.next is None:
                return None
            fast, slow = fast.next.next, slow.next
            if fast == slow:
                break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast