tags: leetcode

143. Reorder List

Introduce:

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

tips:

  • If it's an array, you can use two pointer with L and R to direct order the element. But it's LinkedList now, so you can't left shift R.
  • In this case, you can first reverse the LinkedList which is for R to traverse.
  • First step, find the middle of LinkedList. Be careful for the fast pointer because we want to find the middle's previous point.
  • Step 2: Reverse the m's next LinkedList.[1,2,4,3]
  • To avoid the cycle in step 3(reorder), we will seperate the LinkedList into two pieces.[1,2] [4,3]
  • Step 3: Reorder, not a big deal.
class Solution:
    def reorderList(self, head: ListNode) -> None:
        # find Middle
        fast, slow = head, head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next

        # reverse middle
        curr, prev, next = slow.next, None, None
        while curr != None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        
        #break the linkedlist into two piece to prevent cycle in reorder
        slow.next = None

        # reorder
        L, R = head, prev
        while L and R:
            tmpL = L.next
            tmpR = R.next

            L.next = R
            L = tmpL

            R.next = L
            R = tmpR