[LeetCode-Python版] 876. 链表的中间结点

题目

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

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

题目链接

我的思路

1. 遍历链表，用一个代表序号的变量n和一个字典dic映射每个链表节点的顺序
2. 返回dic[(n+1)//2]

思路不足：

• 空间复杂度是O(N)，因为用了一个长度为N的字典

我的代码

# 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]:
        dic = {}
        cur = head
        n = 1
        while cur:
            dic[n] = cur
            cur = cur.next
            n += 1
        print(n)
        return dic[(n+1)//2]  

题解思路——双指针

1. 定义一个快指针和一个慢指针，快指针每次走两步，慢指针走一步
2. 当快指针为空时，慢指针即为中间节点

参考代码

# 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]:
        if not head or not head.next: return head
        fast = low = head
        while fast and fast.next:
            fast = fast.next.next
            low = low.next
        return low
        

Q&A

1. 双指针解法中，为什么是while fast and fast.next :，如果只用while fast :或 while fast.next :会怎样？

   • 使用 while fast 作为循环条件意味着只要 fast 不是 None，循环就会继续。对于链表长度为奇数的情况，使用while fast会导致 low 超过中间节点。
     例如，有一链表1 -> 2 -> 3 -> 4 -> 5

     • 初始时，low 和 fast 都指向（1）
     • 第一次迭代后，low 指向（2），fast 指向（3）
     • 第二次迭代后，low 指向（3），fast 指向（5）
     • 此时 while fast 仍然为真，进行下一次迭代，low 将指向（4），fast将指向空，退出循环

     由此可见，当链表长度为奇数时，low 最终会指向中间节点的下一个节点，而不是中间节点。

   • 使用 while fast.next 作为循环条件意味着只要 fast.next 不是 None，循环就会继续。如果链表的长度是偶数，它引用一个空对象的属性，从而报错。
     例如，有一链表1 -> 2 -> 3 -> 4

     • 初始时，low 和 fast 都指向（1）
     • 第一次迭代后，low 指向（2），fast 指向（3）
     • 第二次迭代后，low 将指向（3），fast将指向空
     • 下一次循环时，fast是一个空对象，没有next属性，报错

     由此可见，当链表长度为偶数时，使用while fast.next 作为循环条件会报错AttributeError: 'NoneType' object has no attribute 'next'。