Odd Even Linked List

Problem Statement

Given the head of a singly linked list, group all nodes at odd indices together followed by the nodes at even indices, and return the reordered list. The first node is considered odd, the second node is even, and so on. Preserve the relative order within both groups.

Examples

1. Example 1:

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

2. Example 2:

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

Constraints

• The number of nodes in the linked list is in the range [0, 30].
• 0 <= Node.val <= 100
• The linked list is guaranteed to be non-empty.

Follow-up: Could you solve it in O(1) space complexity? O(1) space complexity means that you should not use any extra space except for a few variables.

Hints

• You can use the two-pointer technique to solve this problem.
• The first pointer will be used to traverse the odd nodes, and the second pointer will be used to traverse the even nodes.
• After traversing all the nodes, you can connect the two lists together.

Solution

To solve this problem, you can follow these steps:

1. Initialize two dummy nodes, odd and even, to represent the head of the odd and even linked lists, respectively.
2. Initialize two pointers, oddPtr and evenPtr, to traverse the original linked list.
3. Initialize another pointer, curr, to traverse the original linked list starting from the head.
4. Iterate through the linked list, and for each node:
   • If the index is odd, append the node to the odd list and move oddPtr to the next node.
   • If the index is even, append the node to the even list and move evenPtr to the next node.
5. After traversing all the nodes, connect the even list to the end of the odd list.
6. Return the head of the odd list.

Here's a Python code snippet to illustrate the solution:

`python class Solution: def oddEvenList(self, head: ListNode) -> ListNode: if not head: return head

    odd = ListNode(0)
    even = ListNode(0)
    oddPtr, evenPtr = odd, even
    curr = head
    index = 1

    while curr:
        if index % 2 == 1:
            oddPtr.next = curr
            oddPtr = oddPtr.next
        else:
            evenPtr.next = curr
            evenPtr = evenPtr.next
        curr = curr.next
        index += 1

    evenPtr.next = None
    oddPtr.next = even.next

    return odd.next

`

This solution has a time complexity of O(n) and a space complexity of O(1), where n is the number of nodes in the linked list.