In this post I will try three implementations of the function of interest for LeetCode 328 Odd Even Linked List problem using the Java programming language.
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes!!! You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Constraints: o The relative order inside both the even and odd groups should remain as it was in the input. o The first node is considered odd, the second node even and so on ... o The length of the linked list is between [0, 10^4].
We are given a singly linked list. We need to group all `odd` nodes together followed by the `even` nodes. Please note the definition of what makes a node `odd` and `even`. It is not the value in the node but the position of the node in the linked list.
It seems that we must implement our solution in O(n) time and O(1) space.
If interested in this problem, I suggest you take a look at the problem definition in the LeetCode website to make sure there have been no updates.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
}
}
LeetCode provides the class definition for ListNode which is used to manipulate the linked list. Since I am going to develop the code on a Windows computer using the VSCode IDE, I will have to implement such a class. Please note that it is NOT PART OF THE SOLUTION!
The signature for the function of interest matches the requirements for the problem. The head of the linked list is provided and the function must return a linked list with the `odd` numbered nodes before the `even` number nodes. Please make sure you understand what makes a node in the linked list `odd` or `even`.
1,2,3,4,5 main <<< arr: [1, 2, 3, 4, 5] main <<< input: 1->2->3->4->5 main <<< oddEvenList0: 1->3->5->2->4 main <<< oddEvenList1: 1->3->5->2->4 main <<< oddEvenList2: 1->3->5->2->4 main <<< oddEvenList: 1->3->5->2->4 1,2,3,4,5,6 main <<< arr: [1, 2, 3, 4, 5, 6] main <<< input: 1->2->3->4->5->6 main <<< oddEvenList0: 1->3->5->2->4->6 main <<< oddEvenList1: 1->3->5->2->4->6 main <<< oddEvenList2: 1->3->5->2->4->6 main <<< oddEvenList: 1->3->5->2->4->6 1,2,3,4,5,6,7 main <<< arr: [1, 2, 3, 4, 5, 6, 7] main <<< input: 1->2->3->4->5->6->7 main <<< oddEvenList0: 1->3->5->7->2->4->6 main <<< oddEvenList1: 1->3->5->7->2->4->6 main <<< oddEvenList2: 1->3->5->7->2->4->6 main <<< oddEvenList: 1->3->5->7->2->4->6 1 main <<< arr: [1] main <<< input: 1 main <<< oddEvenList0: 1 main <<< oddEvenList1: 1 main <<< oddEvenList2: 1 main <<< oddEvenList: 1 1,2 main <<< arr: [1, 2] main <<< input: 1->2 main <<< oddEvenList0: 1->2 main <<< oddEvenList1: 1->2 main <<< oddEvenList2: 1->2 main <<< oddEvenList: 1->2 1,2,3 main <<< arr: [1, 2, 3] main <<< input: 1->2->3 main <<< oddEvenList0: 1->3->2 main <<< oddEvenList1: 1->3->2 main <<< oddEvenList2: 1->3->2 main <<< oddEvenList: 1->3->2 1,2,3,4 main <<< arr: [1, 2, 3, 4] main <<< input: 1->2->3->4 main <<< oddEvenList0: 1->3->2->4 main <<< oddEvenList1: 1->3->2->4 main <<< oddEvenList2: 1->3->2->4 main <<< oddEvenList: 1->3->2->4
Test cases are separated from others by two blank lines.
The first line of a test case is used by the test scaffold to populate an array of integers. The contents of the array are then displayed to make sure that the input line and the contents of the array `arr` match.
The test scaffold then generates and displays the contents of the linked list generated from the contents of the `arr` integer array. We have a final chance to verify that the input line matches the contents of the linked list. We are ready to call the function of interest.
Note that we have three implementations of the function of interest. After each implementation is called, the returned linked list is displayed. Note that in all cases the `odd` nodes were displayed before the `even` nodes.
The three implementations are quite similar. The idea was to experiment. The execution times are O(n) and space is O(1).
/**
* Test scafolding
* !!! NOT PART OF SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reder ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and split node values ****
String[] strs = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// **** convert string array to integer array ****
int[] arr = Arrays.stream(strs).mapToInt(Integer::parseInt).toArray();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** populate linked list ****
ListNode head = populate(arr);
// ???? ????
System.out.println("main <<< input: " + display(head));
// **** generate odd even linked list ****
head = oddEvenList0(head);
// **** display odd even linked list ****
System.out.println("main <<< oddEvenList0: " + display(head));
// **** populate linked list ****
head = populate(arr);
// **** generate odd even linked list ****
head = oddEvenList1(head);
// **** display odd even linked list ****
System.out.println("main <<< oddEvenList1: " + display(head));
// **** populate linked list ****
head = populate(arr);
// **** generate odd even linked list ****
head = oddEvenList2(head);
// **** display odd even linked list ****
System.out.println("main <<< oddEvenList2: " + display(head));
// **** populate linked list ****
head = populate(arr);
// **** generate odd even linked list ****
head = oddEvenList(head);
// **** display odd even linked list ****
System.out.println("main <<< oddEvenList: " + display(head));
}
Not much to add to the description of the test scaffold. Note that for each invocation of the function of interest, the same linked list is provided as an argument.
/**
* Nodes for linked list
*/
class ListNode {
// **** members ****
int val;
ListNode next;
// **** constructor(s) ****
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// **** ****
@Override
public String toString() {
return "" + this.val;
}
}
This is the implementation of the ListNode class. I believe that the only information used by the different implementations is the ListNode next class member. At any point the implementations allocate a node.
As I am generating this post I decided to try out one additional approach that would be somewhat different and would allocate and free `even` nodes. I will take a few minutes to implement and test it … OK, I am done. The code is not quite elegant as one of the previous implementations, and the results are quite similar. It was worth giving it a try!
/**
* Populate linked list from the contents of the specified array.
*
* !!! NOT PART OF SOLUTION !!!
*/
static ListNode populate(int[] arr) {
// **** sanity ckeck(s) ****
if (arr.length == 0) return null;
// **** initialization ****
ListNode h = null;
// **** traverse array adding nodes to the linked list ****
for (int i = arr.length - 1; i >= 0; i--) {
h = new ListNode(arr[i], h);
}
// **** return head of linkned list ****
return h;
}
This code IS NOT PART OF THE SOLUTION! The test scaffold used it to populate the linked list with the input array `arr`.
/**
* Display linked list.
*
* !!! NOT PART OF SOLUTION !!!
*/
static String display(ListNode head) {
// **** sanity check(s) ****
if (head == null) return "";
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** traverse link list ****
for (ListNode p = head; p != null; p = p.next) {
sb.append(p.val);
if (p.next != null)
sb.append("->");
}
// **** ****
return sb.toString();
}
This code IS ALSO NOT PART OF THE SOLUTION! I use it to display the linked lists during development and testing.
/**
* Given a singly linked list,
* group all odd nodes together followed by the even nodes.
*
* Execution: O(n) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.9 MB, less than 22.15% of Java online submissions.
*/
static ListNode oddEvenList0(ListNode head) {
// **** sanity checks ****
if (head == null) return null;
if (head.next == null) return head;
// **** initialization ****
ListNode p = null;
ListNode q = null;
ListNode evenHead = null;
ListNode evenTail = null;
int i = 1;
// **** traverse the linked list O(n) ****
for (p = head; p != null; i++) {
// **** check we do NOT need to move this node ****
if (i % 2 == 1) {
q = p;
p = p.next;
continue;
}
// **** remove p from linked list ***
q.next = p.next;
p.next = null;
// **** insert p to even linked list ****
if (evenHead == null) {
evenHead = p;
evenTail = evenHead;
} else {
evenTail.next = p;
evenTail = p;
}
// **** update p ****
p = q.next;
}
// **** append even to odd linked list****
q.next = evenHead;
// **** return odd-even linked list ****
return head;
}
This is the first of four implementations of the function of interest.
The idea is to traverse the input linked list, keep track of odd and even nodes, remove the `even` nodes and insert them in a different linked list. This is done in the loop.
After the loop we link the last node of the linked list holding the `odd` nodes with the linked list holding the `even` nodes.
The head of the initial linked list is then returned.
Please take a look at the comments section of this function. It meets requirements and executes in 0 ms which is not bad at all. Perhaps we should have declared success and moved on to the next problem.
/**
* Given a singly linked list,
* group all odd nodes together followed by the even nodes.
*
* Execution: O(n) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.6 MB, less than 52.56% of Java online submissions.
*
* 70 / 70 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.6 MB
*/
static ListNode oddEvenList1(ListNode head) {
// **** sanity check(s) ****
if (head == null) return null;
if (head.next == null) return head;
// **** initialization ****
ListNode evenHead = null;
ListNode evenTail = null;
ListNode p = head;
ListNode e = head.next;
// **** ****
while (p.next != null) {
// **** point to next even node ****
e = p.next;
// **** point to next odd node ****
p.next = e.next;
// **** ****
if (e.next != null)
p = e.next;
// **** move even node to even list ****
if (evenHead == null)
evenHead = e;
else
evenTail.next = e;
// **** update even next node ****
e.next = null;
// **** update even tail ****
evenTail = e;
}
// **** append even to odd linked list ****
p.next = evenHead;
// **** return head of odd-even linked list ****
return head;
}
In this implementation the approach is similar to the previous one. The code is slightly different but the idea is the same. Leave the `odd` nodes in the input linked list. Remove the `even` nodes and put them in an auxiliary linked list. After the loop, we append the auxiliary linked list with the `even` nodes to the list with the `odd` nodes.
Please check the comments section to verify that the execution time is the same as in the previous implementation.
/**
* Given a singly linked list,
* group all odd nodes together followed by the even nodes.
*
* Execution: O(n) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.4 MB, less than 79.60% of Java online submissions.
*
* 70 / 70 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 38.4 MB
*/
static ListNode oddEvenList2(ListNode head) {
// **** sanity check(s) ****
if (head == null) return null;
if (head.next == null) return head;
// **** initialization ****
ListNode evenHead = null; // even linked list head
ListNode evenTail = null; // even linked list tail
ListNode tail = null; // input list tail node
// **** traverse the input linked list ****
for (ListNode p = head; p != null; p = p.next) {
// **** check if we are done traversing the linked list ****
if (p.next == null) {
tail = p;
break;
}
// **** point to next even node ****
ListNode even = p.next;
// **** set tail of linked list ****
if (even.next == null) tail = p;
// *** skip the even node ****
p.next = even.next;
// **** add even node to tail of evenHead ****
even = new ListNode(even.val);
// **** update the head and tail of the even linked list ****
if (evenHead == null) {
evenHead = even;
evenTail = even;
} else {
evenTail.next = even;
evenTail = even;
}
}
// **** append even to odd linked list ****
tail.next = evenHead;
// **** return head of odd-even linked list ****
return head;
}
In this implementation which is the one I tried a few minutes ago, we add a new `even` node to the auxiliary linked list and let the garbage collector free the original `even` node. Besides that, everything is quite similar to previous implementations. Note that the code is not too elegant.
Take a look at the comments section of this function. The execution time remains at 0 ms and the space is still O(1).
/**
* Given a singly linked list,
* group all odd nodes together followed by the even nodes.
*
* Execution: O(n) - Space: O(1)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.9 MB, less than 22.15% of Java online submissions.
*/
static ListNode oddEvenList(ListNode head) {
// **** sanity check(s) ****
if (head == null) return null;
if (head.next == null) return head;
// **** initialization ****
ListNode odd = head; // first odd node
ListNode even = head.next; // first odd node
ListNode evenHead = even; // first even node
// **** traverse the linked list ****
while (even != null && even.next != null) {
// **** point to next odd node ****
odd.next = even.next;
odd = odd.next;
// **** point to next even node ****
even.next = odd.next;
even = even.next;
}
// **** append even to odd linked list ****
odd.next = evenHead;
// **** return head of odd-even linked list ****
return head;
}
This is the last implementation of this function. The ideas are the same. The implementation is cleaner and more elegant. If you take a look at the comments section you can see we are still at 0 ms for execution time.
In my humble opinion, when dealing with linked lists in general, C and C++ implementations seem to be simpler and faster.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named OddEvenLinkedList.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John