328. Odd Even Linked List

Problem Description

Given the head of a singly linked list, we are tasked to reorder it in a specific way. We have to rearrange the nodes such that those at the odd positions (1st, 3rd, 5th, etc.) come before those at the even positions (2nd, 4th, 6th, etc.). It's important to maintain the original relative order of the nodes within the odd group and within the even group. For example, if the original linked list is 1 -> 2 -> 3 -> 4 -> 5, after reordering it should look like 1 -> 3 -> 5 -> 2 -> 4. This reordering needs to be achieved with certain efficiency constraints: we can't use extra storage space, meaning we must rearrange the nodes in-place, and we must do it with a time complexity of O(n), where n is the number of nodes in the linked list.

Intuition

To solve this problem efficiently, we exploit the in-place nature of linked list reordering. Instead of creating new lists or arrays which would require extra space, we can carefully rearrange the nodes by modifying their next pointers.

The approach is to create two pointers, one that will traverse the odd nodes (a in the solution code) and another for the even nodes (b). The pointers essentially alternate, where a progresses to the node pointed to by b.next and b then moves to the node pointed to by the updated a.next. This way, a is skipping over the even nodes to link together all the odd nodes, and b does the same among the even nodes. This also maintains the original relative order within each subgroup of nodes.

After the loop, all odd-indexed nodes and even-indexed nodes are grouped separately, but we need to link the last node of the odd nodes to the first of the even nodes. To facilitate this, before starting the reordering process, we keep a separate pointer, c, at the first even node. When the reordering is complete (which is when b or b.next is None, indicating the end of the list), we simply link the last node of the odd-indexed group (pointed to by a) to the first of the even-indexed group (pointed to by c). At this point, our reordering is complete and we can return the head of the modified list as the final output.

Learn more about Linked List patterns.

Solution Approach

The implementation of the solution follows a specific pattern where the nodes are reordered in-place using only a few pointers, without the need for additional data structures:

First, we initialize three pointers:
- a, which starts at the head of the list and will be used to iterate over odd indexed nodes.
- b, which starts at the second node (head.next) and will be used to iterate over even indexed nodes.
- c, which keeps track of the head of the even indexed sublist (also starts at head.next).
We enter a loop that continues until either b is None (meaning we've reached the end of the list) or b.next is None (meaning there are no more odd nodes to process since odd nodes are followed by even nodes).
Inside the loop:
- We link a.next to b.next, which is effectively connecting the current odd-indexed node to the next odd-indexed node (a.next skips an even node).
- We update a to be a.next so that it now points to the next odd-indexed node.
- We link b.next to a.next, since a has advanced one step, a.next is now an even-indexed node, and we need to skip an odd node.
- We update b to be b.next to move to the next even-indexed node.
After the loop, all odd nodes are now connected, and a points to the last odd node. We set a.next to c, which links the end of the odd-indexed sublist to the head of the even-indexed sublist we tracked earlier.
Finally, we return head, which now points to the reordered list where odd-indexed nodes are grouped at the beginning, followed by even-indexed nodes.

The above steps conform to the given constraints of O(1) extra space complexity (since we're not using any additional data structures) and O(n) time complexity (we go through the list at most twice, once for odd nodes and once for even nodes).

The successful execution of this pattern depends heavily on the understanding of linked list structure and careful manipulation of next pointers, which allows us to make changes in place.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the provided solution approach with a small example to illustrate the method. Suppose we have a linked list:

1 -> 2 -> 3 -> 4

We set up our three pointers:
- a starts at 1 (head of the list).
- b starts at 2 (second node, head.next).
- c also starts at 2 (head of the even sublist).
Enter the loop. Currently, b is not None nor is b.next None, so we proceed.
First iteration:
- Link a.next (1’s next) to b.next (3). Now the list looks like: 1 -> 3 -> 4
- Move a to a.next (now a is at 3).
- Since a moved, we now update b.next (2’s next) to a.next which does not change anything since a.next is still 4.
- Move b to b.next (now b is at 4).

The list now effectively looks like this, with the pointers at their respective positions (a = 3, b = 4, c = 2):

1 -> 3 -> 4 -> 2 -> NULL

Continue the loop. Now, b.next is None, we exit the loop.
Connect the last odd node (a, now at 3) to the head of the even sublist (c, which is still at 2): 3 -> 2. The list now becomes:

1 -> 3 -> 2 -> 4 -> NULL

Finally, return the head of the reordered list, which is still at 1. The fully reordered list, illustrating odd-positioned nodes followed by even-positioned ones, is now:

1 -> 3 -> 2 -> 4

Each step in this approach closely adheres to the specified pattern, ensuring the final output is achieved with an O(n) time complexity and without using any extra space. The list provided has been reordered in place effectively.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    # Function to rearrange nodes of a given linked list such that all
9    # the odd indexed nodes appear before all the even indexed nodes.
10    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
11        # If the list is empty, nothing needs to be done.
12        if head is None:
13            return None
14      
15        # Initialize two pointers, one for odd indexed nodes (odd_ptr)
16        # and one for even indexed nodes (even_ptr), and also keep track of
17        # the start of even indexed nodes (even_head).
18        odd_ptr = head
19        even_ptr = even_head = head.next
20      
21        # Traverse the list, rearranging the nodes.
22        while even_ptr and even_ptr.next:
23            # Make the next of odd_ptr link to the node after the next 
24            # (effectively the next odd indexed node).
25            odd_ptr.next = even_ptr.next
26            # Move the odd_ptr to its new next.
27            odd_ptr = odd_ptr.next
28          
29            # Connect the next of even_ptr to the node after the next 
30            # (effectively the next even indexed node).
31            even_ptr.next = odd_ptr.next
32            # Move the even_ptr to its new next.
33            even_ptr = even_ptr.next
34      
35        # After all the odd indexed nodes have been linked, append
36        # the even indexed nodes to the end of the list formed by odd indexed nodes.
37        odd_ptr.next = even_head
38      
39        # Return the rearranged list.
40        return head
41

1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    public ListNode oddEvenList(ListNode head) {
13        // If the list is empty, return null.
14        if (head == null) {
15            return null;
16        }
17      
18        // Initialize pointers for manipulation.
19        // 'odd' points to the last node in the odd-indexed list.
20        // 'even' points to the last node in the even-indexed list.
21        // 'evenHead' points to the first node of the even-indexed list.
22        ListNode odd = head;
23        ListNode even = head.next;
24        ListNode evenHead = even;
25      
26        // Iterate over the list to rewire nodes.
27        while (even != null && even.next != null) {
28            // Link the next odd node.
29            odd.next = even.next;
30            // Move the 'odd' pointer to the next odd node.
31            odd = odd.next;
32          
33            // Link the next even node.
34            even.next = odd.next;
35            // Move the 'even' pointer to the next even node.
36            even = even.next;
37        }
38      
39        // After reordering, attach the even-indexed list to the end of the odd-indexed list.
40        odd.next = evenHead;
41      
42        // Return the head of the modified list.
43        return head;
44    }
45}
46

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* oddEvenList(ListNode* head) {
14        // If the list is empty, just return an empty list
15        if (!head) {
16            return nullptr;
17        }
18      
19        // Use 'oddTail' to keep track of the last node in the odd-indexed nodes
20        ListNode* oddTail = head;
21        // Use 'evenHead' and 'evenTail' to keep track of the even-indexed nodes
22        ListNode *evenHead = head->next, *evenTail = evenHead;
23      
24        // Iterate as long as there are even nodes to process
25        while (evenTail && evenTail->next) {
26            // Connect the odd nodes
27            oddTail->next = evenTail->next;
28            oddTail = oddTail->next;
29          
30            // Connect the even nodes
31            evenTail->next = oddTail->next;
32            evenTail = evenTail->next;
33        }
34      
35        // Attach the even nodes to the end of the odd nodes
36        oddTail->next = evenHead;
37      
38        // Return the reorganized list
39        return head;
40    }
41};
42

1// This is the TypeScript type definition for a singly-linked list node.
2type ListNode = {
3  val: number;
4  next: ListNode | null;
5};
6
7/**
8 * This function reorders a singly-linked list by separating it into odd-indexed
9 * nodes and even-indexed nodes and then concatenating the even-indexed nodes
10 * to the end of the odd-indexed nodes.
11 * @param {ListNode | null} head - The head node of the linked list.
12 * @return {ListNode | null} - The head of the modified list with odd and even nodes separated.
13 */
14function oddEvenList(head: ListNode | null): ListNode | null {
15  // Return null if the list is empty.
16  if (!head) {
17    return null;
18  }
19
20  // Initialize pointers to manage the odd and even parts of the list.
21  let odd: ListNode = head; // Points to the last node in the odd list.
22  let even: ListNode | null = head.next; // Points to the first node in the even list.
23  let evenHead: ListNode | null = head.next; // Keeps track of the head of the even list.
24
25  // Iterate over the list to separate nodes into odd and even lists.
26  while (even && even.next) {
27    odd.next = even.next; // Link next odd node.
28    odd = odd.next; // Move odd pointer to the next node.
29    even.next = odd.next; // Link next even node.
30    even = even.next; // Move even pointer to the next node.
31  }
32
33  // Attach the even list to the end of the odd list.
34  odd.next = evenHead;
35
36  // Return the head of the modified list.
37  return head;
38}
39

Time and Space Complexity

The given Python code reorders a linked list so that all the odd nodes are listed before the even nodes, maintaining their relative order. To analyze the time complexity and space complexity of the function oddEvenList, let's go through it step by step:

Time Complexity:

The while loop continues until it has traversed all the nodes of the linked list because it stops only when b is None (meaning the end of the list) or b.next is None (meaning the last node is reached).
Inside the loop, operations have a constant time complexity (O(1)), which includes assigning next pointers for a and b.
Since each node is visited once during the traversal, the total time complexity is based on the number of nodes in the linked list (n). Therefore, the time complexity is O(n) where n is the number of nodes in the linked list.

Space Complexity:

The algorithm only uses a constant amount of extra space for pointers a, b, and c irrespective of the size of the input linked list.
No additional data structures are used that grow with the input size.
Therefore, the space complexity is O(1) constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know