Given a singly linked list, group all odd nodes together followed by the even no

Question

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. Ex: Given: HEAD rightarrow (Nodel) rightarrow (Node2) rightarrow (Node3) rightarrow (Node4) rightarrow (Node5) rightarrow NULL, Return: HEAD rightarrow (Nodel) rightarrow (Node3) rightarrow (Node5) rightarrow (Node2) rightarrow (Node4) rightarrow NULL, The first node is considered odd, the second node even and so on... Programming example: The relative order inside both the even and odd groups should remain as it was in the input.

Explanation / Answer

public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while(odd.next != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
public ListNode oddEvenList(ListNode head)
{
//Check that there are AT LEAST TWO ELEMENTS
if (head == null || head.next == null)
return head;

//Initialize pointers
ListNode lastOdd = head;
ListNode lastEven = head.next;
ListNode firstEven = lastEven;

//Continue as long as there is at least two more elements
while (lastOdd.next != null && lastEven.next != null)
{
//Connect the last odd element with the element next to the
//last even one (such element is odd)
lastOdd.next = lastEven.next;
//Advance lastOdd to such element
lastOdd = lastOdd.next;

//Do the same for the even list, only inverting the roles
lastEven.next = lastOdd.next;
lastEven = lastEven.next;
}

//Now connect the last odd element with the first even element
//This join the two list together
lastOdd.next = firstEven ;

return head;
}

  
  
  

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.