Leetcode 328. Odd Even Linked List

Problem Explanation

This problem involves re-ordering the nodes of a singly linked list such that all odd-numbered nodes are grouped together, followed by all even-numbered nodes. It's important to note that the ordering used here is about the node positions, not their values.

For example, if the given input is 1->2->3->4->5->NULL, which represents a singly linked list where node 1 has value 1, node 2 has value 2, and so on. The output should be 1->3->5->2->4->NULL, which means the odd-numbered nodes (1, 3, 5) are grouped first, followed by the even-numbered nodes (2, 4).

We are required to solve this in place, i.e., without using extra space, and so the space complexity requirement is O(1). Also, the solution should run in O(nodes) time complexity, which means the time required should be proportional to the number of nodes in the list.

Solution Approach

The solution uses two pointers, odd and even, to create two separate lists: one for odd nodes, and one for even nodes. The odd pointer is initialized to the head of the linked list (since the first node is considered odd), and the even pointer is initialized to the second node.

These pointers are moved across the list, with the odd pointer skipping the even nodes and even pointer skipping the odd nodes. In each iteration, the odd pointer moves to the next odd node, and even pointer moves to the next even node.

The key aspect of this approach is to maintain the original order of nodes in both odd and even lists.

At the end of this process, the two lists are concatenated, with the odd list coming first.

The input 1->2->3->4->5->NULL will be transformed as follows

1
2
3# Original List
41->2->3->4->5->NULL
5
6# Odd list
71->3->5
8
9# Even list
102->4
11
12# Final re-ordered list
131->3->5->2->4->NULL

Let's describe the solution in different languages.

Python Solution

1
2python
3class Solution:
4    def oddEvenList(self, head):
5        if not head:
6            return head
7        
8        odd = head
9        even = head.next
10        even_head = even
11        
12        while even and even.next:
13            odd.next = even.next
14            odd = odd.next
15            even.next = odd.next
16            even = even.next
17            
18        odd.next = even_head
19        return head

In the Python solution, we first check if the head is not None because an empty list doesn't need re-ordering. Then, we proceed to create two separate lists using the given approach.

Java Solution

1
2java
3public class Solution {
4    public ListNode oddEvenList(ListNode head) {
5        if (head == null) return null;
6        ListNode odd = head, even = head.next, evenHead = even;
7        while (even != null && even.next != null) {
8            odd.next = even.next;
9            odd = odd.next;
10            even.next = odd.next;
11            even = even.next;
12        }
13        odd.next = evenHead;
14        return head;
15    }
16}

In the Java solution, we are again checking if the head is not null before proceeding with the re-ordering. The Java's null is equivalent to Python's None. The rest of the solution follows the same approach explained earlier.

JavaScript Solution

1
2javascript
3var oddEvenList = function(head) {
4    if (head === null) return null;
5    let odd = head, even = head.next, evenHead = even;
6    while (even !== null && even.next !== null) {
7        odd.next = even.next;
8        odd = odd.next;
9        even.next = odd.next;
10        even = even.next;
11    }
12    odd.next = evenHead;
13    return head;
14};

The JavaScript solution works in the exact same way as the Python and Java solutions. It starts by checking if the input head is not null (which is JavaScript's equivalent to None or null) and then follows the same approach.

C++ Solution

1
2cpp
3class Solution {
4public:
5    ListNode* oddEvenList(ListNode* head) {
6        if (!head) return NULL;
7        ListNode *odd = head, *even = head->next, *evenHead = even;
8        while (even && even->next) {
9            odd->next = even->next;
10            odd = odd->next;
11            even->next = odd->next;
12            even = even->next;
13        }
14        odd->next = evenHead;
15        return head;
16    }
17};

In C++, we check if head is not NULL (which is C++'s equivalent to Python's None or Java and JavaScript's null), and then we follow the exact approach as explained earlier.

C# Solution

1
2csharp
3public class Solution {
4    public ListNode OddEvenList(ListNode head) {
5        if (head == null) return null;
6        ListNode odd = head, even = head.next, evenHead = even;
7        while (even != null && even.next != null) {
8            odd.next = even.next;
9            odd = odd.next;
10            even.next = odd.next;
11            even = even.next;
12        }
13        odd.next = evenHead;
14        return head;
15    }
16}

The C# solution is also very similar to the solutions in other languages. It begins by checking if head is null, and then the odd and even nodes are separated and finally connected together.## Testing the Code To be sure that the codes are working as expected, we should test them with different inputs and scenarios. Odd number of nodes, even number of nodes, same node values, etc. are good examples to such scenarios.

For Python;

1
2python
3class Node:
4    def __init__(self, x):
5        self.val = x
6        self.next = None
7
8def make_list(arr):
9    dummy = Node(-1)
10    last = dummy
11    for val in arr:
12        last.next = Node(val)
13        last = last.next
14    return dummy.next
15
16def print_list(node):
17    while node:
18        print(node.val, end=" -> ")
19        node = node.next
20    print("NULL")
21
22sol = Solution()
23head = make_list([1, 2, 3, 4, 5])
24head = sol.oddEvenList(head)
25print_list(head)
26
27head = make_list([2, 2, 2, 2, 2])
28head = sol.oddEvenList(head)
29print_list(head)

In this Python test script, make_list function creates linked list from Python list, and print_list function prints linked list nodes one by one. You may create similar ones for other languages.

To finalize, the presented Java, JavaScript, Python, C# and C++ solutions aim to re-arrange linked list nodes. They work in-place and the approach is to use two pointers to separate odd-indexed and even-indexed nodes, and finally connect these two linked lists together. The nodes are separated correctly to satisfy the original relative ordering of odd and even nodes. This approach will help to solve similar linked list related problems with small modifications.