LintCode: Middle of Linked List

Middle of Linked List

Similar Problems:

Find the middle node of a linked list.

Given 1->2->3, return the node with value 2.

Given 1->2, return the node with value 1.

Instead of solving it by two-pass. Can you do it in one-pass?


Credits To:

Leave me comments, if you have better ways to solve.

  • Solution:
## Blog link:
## Basic Ideas: fast/slow pointers
## Complexity: Time O(n), Space O(1)
Definition of ListNode
class ListNode(object):

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

class Solution:
    @param: head: the head of linked list.
    @return: a middle node of the linked list
    def middleNode(self, head):
        slow, fast = head, head
        while fast and and
            slow =
            fast =
        return slow

Original URL:

Connect with Denny In LinkedIn Or Slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.