Middle of the Linked List-CodePudding

In the code below, when using two pointers technique, it's confusing that why we use slow.next and fast.next.next. For example in the linked list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], if we are in the last position '10' (fast pointer), the slow pointer should be in the '8' position. Could someone please clarify that?

def middleNode(self, head):
        slow = fast = head 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        return slow

CodePudding user response：

In short: fast moves at double speed of slow. Their distance increases at each iteration by one. This is different than moving with the same velocity but starting different positions (say one starts at 0 and the other at 2).

More detailed explanation:

The fast pointer moves with double the speed of the slow pointer, that's why when the fast pointer reaches the end of the linked list, the slow pointer is in the middle. That's the reason why the fast pointer moves fast.next.next. This means that fast skips one and jumps 2 fields in each iteration, while the slow pointer only moves one. That's also the reason you check fast and fast.next in the while loop condition, to make sure the next pointer is not None, because you want to call next on it.

Let's take a smaller example then you have provided to make illustration easier:

[1,2,3,4,5]

# before entering the while loop:
# head is at position 1
# fast and slow both are at position 1

# first iteration
[1,2,3,4,5]
 f
 s
fast == 1 and fast.next == 2
slow == 1
fast jumps 2 nodes and becomes 3 (fast.next.next)
slow jumps 1 node and becomes 2 (slow.next)

# second iteration
[1,2,3,4,5]
     f
   s
fast == 3 and fast.next == 4
slow == 2
fast jumps 2 nodes and becomes 5 (fast.next.next)
slow jumps 1 node and becomes 3 (slow.next)

# third iteration (doesn't enter the loop, see why)
[1,2,3,4,5]
         f
     s
fast == 5 and fast.next == None (tail of linked list)
slow == 3
# while loop breaks
# we return slow which lies in the middle of the linked list