返回单链表后半段元素（取第二中间节点）代码问题排查

给定单链表，返回链表后半段元素；如果链表存在两个中间节点，选取第二个中间节点作为后半段起始节点。

• 测试样例：链表结构为1->2->3->4->5（对应元素列表[1,2,3,4,5]），期望输出为[3,4,5]。

• 第一次遍历计算链表长度时，直接移动了传入的原始head指针，遍历结束后head已经指向空值None，第二次遍历的循环条件while head != None从一开始就不成立，循环完全不会执行。
• 节点位置计数逻辑错误：长度为5的链表，目标中间节点是从头数第3个（索引从0开始对应下标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]:
        # 第一次遍历统计链表长度，用临时变量遍历，不修改原始head指针
        length = 0
        cur = head
        while cur is not None:
            length += 1
            cur = cur.next
        # 计算需要移动的步数，长度整除2刚好是到目标节点的移动步数
        move_step = length // 2
        cur = head
        for _ in range(move_step):
            cur = cur.next
        return cur

不需要提前统计链表长度，用两个指针一次遍历即可找到中间节点，空间复杂度O(1)：

• 慢指针每次走1步，快指针每次走2步
• 当快指针走到链表末尾（快指针为空或快指针的next为空）时，慢指针刚好落在要求的中间节点位置

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

内容的提问来源于stack exchange，提问作者Shivam Pandey