Leetcode 143. Reorder List. Python

 143. Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Solution :

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        
        # searching middle
        s, f = head, head.next
        while f and f.next:
            s = s.next
            f = f.next.next
            
        # second half reversing
        sec = s.next
        prev = s.next = None
        while sec:
            temp = sec.next
            sec.next = prev
            prev = sec
            sec = temp
            
        # merging both
        fir, sec = head, prev
        while sec :
            t1, t2 = fir.next, sec.next
            fir.next = sec
            sec.next = t1
            fir, sec = t1, t2

Explaination :