0143: Reorder List

Problem Statement

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.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 104].
  • 1 <= Node.val <= 1000

Code Solution

class Solution:
    def reorderList(self, head):
        if not head:
            return None
            
        lsl = head
        rsl = None
        
        slow = head
        fast = head.next
        while slow and fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        rsl = slow.next
        slow.next = None
        
        def rec(node):
            prev = None
            curr = node
            while curr:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp
            return prev
        
        rsl = rec(rsl)
        
        lptr = lsl
        while rsl:
            temp = rsl.next
            rsl.next = lptr.next
            lptr.next = rsl
            lptr = lptr.next.next
            rsl = temp
        
        return lsl