Odd Even Linked List

Question

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1:

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

Example 2:

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

Solution

Intuition

Same concept as Swap nodes in pairs.

We use 3 variable to keep track of: pivot, oddTail and evenTail

All we need to is then:

oddTail -> pivot
evenTail -> pivot.next

We then just need to move

oddTail = oddTail.next
evenTail = evenTail.next
pivot = pivot.next.next

And then repeat

oddTail -> pivot
evenTail -> pivot.next

Which is also equivalent to this:

Now we just need to do

pivot -> evenHead

Implementation

class App: 
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if (head is None or head.next is None or head.next.next is None):
            return head
        
        oddTail = head
        evenTail = head.next
        pivot = head.next.next

        evenHead = head.next

        while (pivot):
            oddTail.next = pivot
            evenTail.next = pivot.next

            pivot = pivot.next.next if pivot.next is not None else None

            oddTail = oddTail.next
            evenTail = evenTail.next

        oddTail.next = evenHead

        return head

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