Leetcode 876:链表的中间结点(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 876:链表的中间结点(超详细的解法!!!)

in leetcode with 0 comment

给定一个带有头结点head的非空单链表,返回链表的中间结点。

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

示例 1:

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2:

输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。

提示:

解题思路

这个问题可以使用快慢指针处理,在之前的问题Leetcode 141:环形链表中使用过。快指针fast每次移动两步,慢指针slow每次移动一步。同时移动fastslow,如果链表中包含奇数个节点,例如:

1  2  3  4  5  null
   ↑     ↑
  slow  fast

此时返回slow.next即可。如果链表包含偶数个节点,例如:

1  2  3  4  5  6  null
      ↑        ↑
     slow     fast

此时返回slow即可。

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

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses