LintCode 228 [Middle of Linked List]

原题

找链表的中点。

样例
链表 1->2->3的中点是2。链表 1->2的中点是1。

解题思路

• 快慢指针一起跑，快的到终点，慢的到中点

完整代码

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""

class Solution:
    # @param head: the head of linked list.
    # @return: a middle node of the linked list
    def middleNode(self, head):
        # Write your code here
        if head is None or head.next is None:
            return head
            
        slow, fast = head, head.next
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            
        return slow