leetcode876-- Middle of the Linked List(快慢指针法)

leetcode876-- Middle of the Linked List(快慢指针法)

题目

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

 

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

 

Note:

    The number of nodes in the given list will be between 1 and 100.


题目的意思是返回两个link的中间的link,注意中间link是从中间的那个开始往后的连在一块儿的,

这个题目的想法是快慢指针法,即一个快指针一个慢指针,快指针一次走两步(前提是走一步还有元素的情况下),慢指针是一次走一步,那么当快指指针走到头的时候慢指针就到了中间的节点


class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast = head
        slow = head
        
        while fast:
            fast = fast.next
            if not fast:
                break
            else:
                fast = fast.next
            slow = slow.next
        
        return slow

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦