Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Odd Even Linked List

Problem Statement

Group the nodes in odd positions together, followed by the nodes in even positions, keeping the order inside each group, and return the head. Only the links may change.

Examples

Example 1

  • Input: head = [1, 2, 3, 4, 5]
  • Expected Output: [1, 3, 5, 2, 4]

Example 2

  • Input: head = [2, 1, 3, 5, 6, 4, 7]
  • Expected Output: [2, 3, 6, 7, 1, 5, 4]

Example 3

  • Input: head = [1, 2]
  • Expected Output: [1, 2]

The idea

Do not think of it as moving nodes out of one list

.....

.....

.....

Like the course? Get enrolled and start learning!
Sajid Khan

Sajid Khan

· 5 days ago

// Solution by keeping a reference to the most recently modified odd value, which continues to point to the first even value discovered

oddEvenList(head) {
    if (head === null || head.next === null) return head;

    let prev = head;
    let even = head.next;

    while (even && even.next) {
      const odd = even.next;

      even.next = even.next.next;
      odd.next = prev.next;
      prev.next = odd

      even = even.next
      prev = odd;
    }

    return head;
}
Show 1 reply

Reading Progress

0%

Vote for new content