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.
Example 1: Input:1->2->3->4->5->NULLOutput:1->3->5->2->4->NULL
Discussion:
This is a fairly straightforward linked list problem. The key thing to keep in mind is that each node object is pointing to another node (if not empty). Therefore this will involve keeping track of nodes while we relink the linked list.
In terms of steps, we keep several pointers and one counter. The counter lets us know whether it’s even or odd number that we’re currently at. We maintain two lists, one for odd and one for even. As we traverse our original list, we assign the nodes to each list. At the end we join both lists together, resulting in a linked list with the odd items first followed by the even items, in original sorted order.
The edge cases are when there is no list passed in, and when there’s only one node in the list passed in. The first is likely more for leetcode handling rather than in real life situations. The second is because we set up an odd list and an even list, but we can’t set that up if there’s only one node.
Steps:
- keep track of
- traversal
- odd nodes tail
- even node tail
- loop through until end (null node) reached
- increment counter and move forward
- add to either odd list or even list
- join both together at end
var oddEvenList = function(head) {
if (head===null) { //no list
return null;
}
if (head.next===null) { //one node
return head;
}
let odd=head;
let even=head.next;
let evenHead=even;
let cur=even;
let count=0;
while (cur.next) {
//console.log(count,cur);
count++;
cur=cur.next;
if (count%2===0) { //even
even.next=cur;
even=even.next;
}
else { //odd
odd.next=cur;
odd=odd.next;
}
}
odd.next=evenHead;
even.next=null;
return head;
};