Hi everybody! Hope you are doing well. It is Thursday evening and I do not know where the week went. We have one more day before the next weekend!
I was looking at singly linked lists in LeetCode and decided to tackle problem 328. Odd Even Linked List. If interested take a look at the requirements.
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 and are asked to separate the nodes that are at odd indices from the ones at the even indices. The first node would be at position 1, the second node at position 2, the third note at position 3 and so on. The values in the node are of no interest.
In addition we are asked to perform the task in O(1) and space complexity O(nodes). This means that we should not create new nodes and should traverse the initial linked list once.
Make sure you take into consideration the constraints.
I will be solving the problem using Java on a Windows 10 computer using the VSCode IDE. Because of this, I will need to generate a test scaffolding to collect data, put it in the format expected by the method we need to develop, call the method and return the results.
/**
* 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) {
}
}
We are given the definition of the ListNode class (which I will have to implement due to the test scaffolding) and the signature for the function / method we need to develop for our solution.
1,2,3,4,5 main <<< arr: [1, 2, 3, 4, 5] main <<< input: 1->2->3->4->5 main <<< oddEvenList: 1->3->5->2->4 main <<< oddEvenList1: 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 <<< oddEvenList: 1->3->5->2->4->6 main <<< oddEvenList1: 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 <<< oddEvenList: 1->3->5->7->2->4->6 main <<< oddEvenList1: 1->3->5->7->2->4->6 1 main <<< arr: [1] main <<< input: 1 main <<< oddEvenList: 1 main <<< oddEvenList1: 1 1,2 main <<< arr: [1, 2] main <<< input: 1->2 main <<< oddEvenList: 1->2 main <<< oddEvenList1: 1->2 1,2,3 main <<< arr: [1, 2, 3] main <<< input: 1->2->3 main <<< oddEvenList: 1->3->2 main <<< oddEvenList1: 1->3->2
The first example is the one provided by LeetCode. The rest I used to make sure all was well before submitting the code.
The first line in each set is the list of integers we will use to build the linked list. It appears that the test scaffolding is processing the input line and generating an array of integers which is then displayed. This is done to assure that we were able to collect and parse the data properly.
After displaying the array of integers the code appears to create and display a linked list. The numbers in the linked list match the order of the numbers in the array and those in the input line. It appears that all is going well so far.
The next line displays a linked list in which the odd position nodes have been collected in the proper order followed by the even numbered nodes.
In addition, it seems that the test scaffolding might be calling a second implementation which appears to produce the same results.
/**
* 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;
}
}
Since I am developing the code on my personal computer, the test scaffolding requires us to implement the ListNode class. This is not part of the solution.
/**
* Test scafolding
*
* @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 buffere 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.print("main <<< input: ");
display(head);
System.out.println();
// **** generate odd even linked list ****
head = oddEvenList(head);
// **** display odd even linked list ****
System.out.print("main <<< oddEvenList: ");
display(head);
System.out.println();
// **** populate linked list ****
head = populate(arr);
// **** generate odd even linked list ****
head = oddEvenList1(head);
// **** display odd even linked list ****
System.out.print("main <<< oddEvenList1: ");
display(head);
System.out.println();
}
We read the input line and split the results into an array of strings each holding the string representation of a single integer value. We then create an array and populate it with the associated integers in the string array. The array is displayed.
We create and populate the linked list using the array of integers. To make sure all is well we then display the linked list. So far, all integers are in the same order. All appears to be fine. For space and time reasons I will not cover in this post the populate() and display() functions / methods. If interested you can find the associated code in the GitHub repository associated with this post.
We then call oddEvenList() function / method with the head of the linked list. The results are displayed. This is the function that I first generated as my solution and was accepted by LeetCode.
We then regenerate a new linked list using the same input data. Since we are somewhat confident we can generate the linked list we do not display it. We then call the oddEvenList1() function / method to produce the same results. After displaying the linked list it seems that both functions work and generate the same results.
Before we get to the code of the two approaches, let’s make sure we understand what is being asked from us. We need to collect the provided order a list of all nodes in odd positions (not values) followed by the nodes in even positions (not values). In all the cases we have the node values matching the positions so it is easier to follow. You can just put a set of random integers and since the code is not dependent on them (as we will see shortly), the ordering should work.
/**
* 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 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;
}
We will split into two different linked lists the nodes in odd and even positions. When done we will concatenate to the odd list the even list. Note that we will traverse the linked list once.
You may note that there is no ‘oddHead’ or ‘oddTail’ variables defined. The reason is that we will keep in the linked list pointed by head all the odd nodes. The even nodes will be moved to the linked list named ‘evenHead’.
The loop starts by checking if we are dealing with an odd position or not. As I am writing this post I feel that the ‘i’ variable should have been named ‘pos’ instead.
So far we have taken care of the nodes in odd positions by just leaving them alone. As a matter of fact we have only dealt with the first odd node. We will now deal with the first even node.
We first remove the node from the provided linked list. We insert the even node into the evenHead linked list.
The last thing we need to do in the loop is to make sure that p is set to the proper value to continue traversing the original (now being modified) linked list.
After the loop we need to append the evenHead linked list to the head linked list which it only has the original odd position nodes.
/**
* 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 oddEvenList1(ListNode head) {
// **** sanity checks ****
if (head == null)
return null;
// **** initialization ****
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
// **** traverse the linked list ****
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
// **** append the even to the odd linked list ****
odd.next = evenHead;
// **** odd-even linked list ****
return head;
}
This is very similar approach but with slightly less code. This is a slightly optimized code using a similar approach.
Of interest in the body of the while loop. I will use Visio to generate a diagram to better understand what is going on…
…Done
The four statements in the loop are labeled in order with letters [a : d]. As you can tell the even nodes are moved to the evenHead list. Please note that one way or the other the odd numbered nodes remain in the original list while the even nodes are moved to the evenHead list.
Please make sure you can follow the next loop. I decided to leave the diagram just after the first iteration is completed. If you have comments or questions regarding the code or diagram please let me know.
/**
* Display linked list.
*
* !!! NOT PART OF SOLUTION !!!
*/
static void display(ListNode head) {
// **** sanity check(s) ****
if (head == null)
return;
// **** traverse the link list ****
for (ListNode p = head; p != null; p = p.next) {
System.out.print(p.val);
if (p.next != null)
System.out.print("->");
}
}
For some reason when I was collecting the information for the post I decided to include the function / method that displays the nodes in the linked list. I find it quite useful to insert call to it in strategic parts of the code to make sure we can properly follow processing.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any otLeether post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 4,993 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com