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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.