Odd Even Linked List medium

Problem Statement

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, the second node is even, and so on.

Note:

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

Steps to Solve

1. Initialization: We need pointers to track the odd and even sublists. Let's call them odd and even. We'll also need pointers to traverse the list, evenHead (to remember the start of the even sublist for later concatenation) and curr (to iterate).

2. Iteration: We iterate through the linked list. If the current node's index is odd, we append it to the odd list. If it's even, we append it to the even list.

3. Concatenation: After iterating, we concatenate the even list to the end of the odd list.

Explanation

The key is to maintain two separate lists—one for odd-indexed nodes and another for even-indexed nodes. We then join these lists at the end. The algorithm cleverly manages pointers to do this in O(1) extra space.

Code (Python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head):
    if not head or not head.next:  # Handle empty or single-node lists
        return head

    odd = head  # Start of odd list
    even = head.next  # Start of even list
    evenHead = even  # Remember the head of the even list

    while even and even.next:  # Iterate until we reach the end of the even list
        odd.next = even.next # Link the odd node to the next odd node.
        odd = odd.next       # Move the odd pointer forward.
        even.next = odd.next #Link the even node to the next even node.
        even = even.next     # Move the even pointer forward.


    odd.next = evenHead  # Connect the end of the odd list to the beginning of the even list.

    return head

# Example usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
result = oddEvenList(head)
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)  # Output: [1, 3, 5, 2, 4]


head2 = ListNode(2,ListNode(1,ListNode(3,ListNode(5,ListNode(6,ListNode(4,ListNode(7))))))
result2 = oddEvenList(head2)
output2 = []
while result2:
    output2.append(result2.val)
    result2 = result2.next
print(output2) # Output: [2, 3, 6, 7, 1, 5, 4]

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate through the list once.
• Space Complexity: O(1). We use a constant number of extra variables to maintain pointers. We don't create any new linked list nodes.