medium Odd Even Linked List

Problem Statement

Given the head of a singly linked list, rearrange the nodes such that all nodes with odd indices are grouped together followed by all nodes with even indices, and return the updated list

The order of the nodes within the odd and even groups should remain as in the original list.

The reordering should be done in-place with extra space and time complexity.

Examples

Example 1:

• Input: head = [10, 20, 30, 40, 50, 60]
• Expected Output: [10, 30, 50, 20, 40, 60]
• Justification: Nodes at indices 1, 3, and 5 are grouped together first (10, 30, 50), followed by nodes at indices 2, 4, and 6 (20, 40, 60).

Example 2:

• Input: head = [1, 3, 5, 7, 9]
• Expected Output: [1, 5, 9, 3, 7]
• Justification: Nodes at indices 1, 3, and 5 are grouped together first (1, 5, 9), followed by nodes at indices 2 and 4 (3, 7).

Example 3:

• Input: head = [2, 4, 6, 8, 10, 12, 14]
• Expected Output: [2, 6, 10, 14, 4, 8, 12]
• Justification: Nodes at indices 1, 3, 5, and 7 are grouped together first (2, 6, 10, 14), followed by nodes at indices 2, 4, and 6 (4, 8, 12).

Constraints:

• The number of nodes in the linked list is in the range [0, 10⁴].
• -10⁶ <= Node.val <= 10⁶

Solution

To solve this problem, we need to rearrange the linked list nodes so that nodes at odd indices come before nodes at even indices. We'll maintain two pointers: one for the odd-indexed nodes and one for the even-indexed nodes. By traversing the list once, we can link all odd-indexed nodes together, and then all even-indexed nodes. Finally, we'll link the last odd-indexed node to the first even-indexed node. This approach works efficiently because it only requires a single pass through the list and uses constant space.

This method is effective because it leverages the existing structure of the linked list and avoids additional space allocation, making it suitable for large datasets.

Step-by-Step Algorithm

• Initialize:

  • Set odd to point to the head of the list.
  • Set even to point to the second node.
  • Store the starting point of the even list in even_head.

• Traverse the list:

  • While there are more nodes to process:
    • Set the next odd node to be the node after the next even node.
    • Move the odd pointer to this next odd node.
    • Set the next even node to be the node after the next odd node.
    • Move the even pointer to this next even node.

• Combine lists:

  • Set the next node of the last odd node to the head of the even list.

Algorithm Walkthrough

Let's walk through the example input [10, 20, 30, 40, 50, 60]:

• Initial setup:

  • odd points to 10
  • even points to 20
  • even_head points to 20

• First iteration:

  • Link odd.next (10) to odd.next.next (30)
  • Move odd to 30
  • Link even.next (20) to even.next.next (40)
  • Move even to 40

• Second iteration:

  • Link odd.next (30) to odd.next.next (50)
  • Move odd to 50
  • Link even.next (40) to even.next.next (60)
  • Move even to 60

• End of list:

  • Link the last odd node (50) to the head of the even list (20)

Code

// class ListNode {
//     int val;
//     ListNode next;

//     ListNode(int x) {
//         val = x;
//         next = null;
//     }
// }

class Solution {

  public ListNode oddEvenList(ListNode head) {
    // If the list is empty, return null
    if (head == null) return null;

    // Initialize pointers for odd and even lists
    ListNode odd = head;
    ListNode even = head.next;
    ListNode evenHead = even; // Store the head of the even list

    // Traverse the list
    while (even != null && even.next != null) {
      // Connect odd nodes
      odd.next = even.next;
      odd = odd.next;

      // Connect even nodes
      even.next = odd.next;
      even = even.next;
    }

    // Connect the end of the odd list to the head of the even list
    odd.next = evenHead;

    // Return the re-ordered list
    return head;
  }

  public static void main(String[] args) {
    // Example 1
    ListNode head1 = new ListNode(10);
    head1.next = new ListNode(20);
    head1.next.next = new ListNode(30);
    head1.next.next.next = new ListNode(40);
    head1.next.next.next.next = new ListNode(50);
    head1.next.next.next.next.next = new ListNode(60);

    Solution solution = new Solution();
    ListNode result1 = solution.oddEvenList(head1);
    printList(result1); // Output: 10 -> 30 -> 50 -> 20 -> 40 -> 60 -> null

    // Example 2
    ListNode head2 = new ListNode(1);
    head2.next = new ListNode(3);
    head2.next.next = new ListNode(5);
    head2.next.next.next = new ListNode(7);
    head2.next.next.next.next = new ListNode(9);

    ListNode result2 = solution.oddEvenList(head2);
    printList(result2); // Output: 1 -> 5 -> 9 -> 3 -> 7 -> null

    // Example 3
    ListNode head3 = new ListNode(2);
    head3.next = new ListNode(4);
    head3.next.next = new ListNode(6);
    head3.next.next.next = new ListNode(8);
    head3.next.next.next.next = new ListNode(10);

    ListNode result3 = solution.oddEvenList(head3);
    printList(result3); // Output: 2 -> 6 -> 10 -> 4 -> 8 -> null
  }

  // Helper method to print the linked list
  public static void printList(ListNode head) {
    while (head != null) {
      System.out.print(head.val + " -> ");
      head = head.next;
    }
    System.out.println("null");
  }
}

Complexity Analysis

Time Complexity

The algorithm traverses the linked list only once, where each node is visited and processed exactly once. Thus, the time complexity is , where n is the number of nodes in the linked list.

Space Complexity

The algorithm rearranges the nodes in place without using any extra data structures that grow with the size of the input. Therefore, the space complexity is .