Segregate even and odd nodes in a Linked List Medium 0 attempts
GeeksforGeeks ↗

Segregate even and odd nodes in a Linked List

Medium Linked List GeeksforGeeks

Given a singly linked list, rearrange its nodes so every node holding an even value appears before every node holding an odd value, while the relative order within each group stays the same as in the original list.

Input Format
Implement segregateEvenOdd(head). Inputs below show JavaScript function arguments; there is no stdin parsing. Linked lists use value arrays. The editor passes nodes with val and next properties; [] becomes null.
Output Format
Return the result described in the statement. Returned list heads are displayed as value arrays; a null head is [].

Sample Input and Output

Example 1 ยท Run Sample

Input
head = [17,15,8,12,10,5,4]
Output
[8,12,10,4,17,15,5]

Example 2

Input
head = [1,3]
Output
[1,3]
Constraints
  • 1 <= N <= 10^4
Test Cases (2)
Case 1
Args: [[17,15,8,12,10,5,4]] Expected: [8,12,10,4,17,15,5]
Case 2
Args: [[1,3]] Expected: [1,3]
Topics
Linked List

Two Lists Merge

javascript
function segregateEvenOdd(head) {
  const even = {next:null}, odd = {next:null};
  let e = even, o = odd, curr = head;
  while (curr) {
    if (curr.val % 2 === 0) { e.next = curr; e = e.next; }
    else { o.next = curr; o = o.next; }
    curr = curr.next;
  }
  o.next = null; e.next = odd.next;
  return even.next;
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript