Group nodes by their index: If there is a singly linked list, based on indexes,
ID: 3799414 • Letter: G
Question
Group nodes by their index:
If there is a singly linked list, based on indexes, group all nodes with odd index first followed
by the nodes with even index.
Example:
Given 0->1->2->3->4->5->NULL
return 1->3->5->0->2->4->NULL
Notes:
1, We are talking about the node number(index) and not the value in the nodes.
2, The relative order inside both the even and odd groups should remain as it was in the
input.
3, The first node is considered even, the second node odd and so on ...
If you can solve the above problem easily, you can try to solve it with one more request
again:
solve the problem above “in place”
Note:
You can find the definition of “in place” in
https://en.wikipedia.org/wiki/In-place_algorithm
Code outline:
// Definition for a node.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
// solution class
public class Solution {
public ListNode oddEvenList(
ListNode head) {
// please add your code here
}
// Do not need to write the main function, I will test the method
//oddEvenList(ListNode head) by myself.
}
Explanation / Answer
public static LinkedList<Integer> seperateEvenAndOddIndexNodes(LinkedList<Integer> head)
{
LinkedList<Integer> prevNode =null, currentNode = head, tail = head, nextNode;
int length = length(head);
int index = 0;
if (length < 3) {
return head;
}
while (tail != null && tail.next() != null) {
tail = tail.next();
}
while (currentNode != null && index < length) {
nextNode = currentNode.next();
if (index % 2 == 1) {
LinkedList<Integer> temp = currentNode;
tail.next(temp);
tail = temp;
prevNode.next(nextNode);
currentNode = prevNode;
temp.next(null);
}
prevNode = currentNode;
currentNode = nextNode;
index++;
}
return head;
}
Define your class as Linear Node type :
public class LinkedList<Integer>
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.