Reorder List

Question 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]

Solution

Note: in the question it's asked you to modify the linked list in-place .

So given a linkedlist of 1 -> 2 -> 3 -> 4, we can do as follows:

1. Separate into 2 heads starting at 1 -> 2 -> None and 4 -> 3 -> None
2. Start from the orginal head, and start connecting 1 head to another

So for example if we have

1 -> 2 -> 3 -> 4

          v
original: 1 -> 2 -> None

reverse:  4 -> 3 -> None
          ^

We can keep connecting the 2 head together and move its corresponding head

So in the end we have the following:

Deciding where to split

Now considering that we have 5 elements: 1 -> 2 -> 3 -> 4 -> 5

We need to decide where to cut the element, weather it's

• 1 -> 2 -> 3 -> None and 5 -> 4 -> None
• or 1 -> 2 -> None and 5 -> 4 -> 3 -> None

Now considering the case where we have:

1 -> 2 -> None
5 -> 4 -> 3 -> None

You would be able to see in here, as the natural of the problem, we cannot have this

It's going to throw NullPointerException when we're trying to map from None -> 3

As a result, we need to go

1 -> 2 -> 3 -> None
5 -> 4 -> None

Which will lead to the following sequence:

Deciding how to split

Since in the case of 1 -> 2 -> 3 -> 4. We want the first half to stop at 2. As a result, we need to use Find half of a linked list but with a condition that the stop is the last item on the left.

We then want to detach this item and start In-place reversal linked list from the first item on the right

Stopping condition check

When connecting all the dots together. Since the normalHead is always behind the reversedHead, we need to check if the reversedHead is not null

Implementation

from dataclasses import dataclass
from typing import *
import unittest

@dataclass
class ListNode:
    val: int
    next: 'ListNode'
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class App:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow, fast = head, head.next

        while (fast and fast.next):
            slow = slow.next
            fast = fast.next.next

        reversedHead = self.reverseLinkedList(slow.next)
        slow.next = None
        

        while reversedHead:
            nextHead, nextReversedHead = head.next, reversedHead.next

            head.next = reversedHead
            head = nextHead

            reversedHead.next = head
            reversedHead = nextReversedHead


    def reverseLinkedList(self, node: ListNode) -> ListNode:
        previousNode = None

        while (node):
            nextNode = node.next
            node.next = previousNode
            previousNode = node
            node = nextNode

        return previousNode

[!note]
For the traversal, we should use 2 pointers from head, and reversedHead to traverse so that it's easy. Do not use currHead and switch between the two it will be harder

Time complexity: $O(n)$
Space complexity: $O(1)$