Odd Even Linked List

This question is asked by Facebook. Given a singly linked list, re-order and group its nodes in such a way that the nodes in odd positions come first and the nodes in even positions come last.

Note: Positions are 1-indexed (first node is at position 1, second node is at position 2, etc.).

Example(s)

Example 1:

Input: 4->7->5->6->3->2->1->NULL
Output: 4->5->3->1->7->6->2->NULL
Explanation:
- Odd positions (1, 3, 5, 7): 4, 5, 3, 1
- Even positions (2, 4, 6): 7, 6, 2
- Result: odd nodes first, then even nodes

Example 2:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Explanation:
- Odd positions (1, 3, 5): 1, 3, 5
- Even positions (2, 4): 2, 4
- Result: odd nodes first, then even nodes

Example 3:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
Explanation:
- Odd positions: 2, 3, 6, 7
- Even positions: 1, 5, 4

Solution

The solution uses two-pointer technique:

Separate into two lists: Create odd list and even list
Traverse and split: Alternate between odd and even positions
Connect lists: Link odd list to even list
Return head: Return the reordered list

JavaScript Solution
Python Solution

JavaScript Solution

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/

/**
* Reorder linked list: odd positions first, then even positions
* @param {ListNode} head - Head of the linked list
* @return {ListNode} - Reordered list head
*/
function oddEvenList(head) {
if (!head || !head.next) {
  return head;
}

// Separate into odd and even lists
let odd = head;           // Points to odd-positioned nodes
let even = head.next;     // Points to even-positioned nodes
const evenHead = even;    // Save head of even list

// Traverse and split
while (even && even.next) {
  // Link odd nodes
  odd.next = even.next;
  odd = odd.next;
  
  // Link even nodes
  even.next = odd.next;
  even = even.next;
}

// Connect odd list to even list
odd.next = evenHead;

return head;
}

// Helper function to create a list node
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val);
this.next = (next===undefined ? null : next);
}

// Helper function to print list
function printList(head) {
const result = [];
while (head) {
  result.push(head.val);
  head = head.next;
}
return result.join('->') + '->NULL';
}

// Test case 1: 4->7->5->6->3->2->1->NULL
const list1 = new ListNode(4);
list1.next = new ListNode(7);
list1.next.next = new ListNode(5);
list1.next.next.next = new ListNode(6);
list1.next.next.next.next = new ListNode(3);
list1.next.next.next.next.next = new ListNode(2);
list1.next.next.next.next.next.next = new ListNode(1);
console.log('Example 1:', printList(oddEvenList(list1)));
// 4->5->3->1->7->6->2->NULL

// Test case 2: 1->2->3->4->5->NULL
const list2 = new ListNode(1);
list2.next = new ListNode(2);
list2.next.next = new ListNode(3);
list2.next.next.next = new ListNode(4);
list2.next.next.next.next = new ListNode(5);
console.log('Example 2:', printList(oddEvenList(list2)));
// 1->3->5->2->4->NULL

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

from typing import Optional

# Definition for singly-linked list.
class ListNode:
  def __init__(self, val=0, next=None):
      self.val = val
      self.next = next

def odd_even_list(head: Optional[ListNode]) -> Optional[ListNode]:
  """
  Reorder linked list: odd positions first, then even positions
  
  Args:
      head: Head of the linked list
      
  Returns:
      ListNode: Reordered list head
  """
  if not head or not head.next:
      return head
  
  # Separate into odd and even lists
  odd = head           # Points to odd-positioned nodes
  even = head.next     # Points to even-positioned nodes
  even_head = even     # Save head of even list
  
  # Traverse and split
  while even and even.next:
      # Link odd nodes
      odd.next = even.next
      odd = odd.next
      
      # Link even nodes
      even.next = odd.next
      even = even.next
  
  # Connect odd list to even list
  odd.next = even_head
  
  return head

# Helper function to print list
def print_list(head: Optional[ListNode]) -> str:
  result = []
  while head:
      result.append(str(head.val))
      head = head.next
  return '->'.join(result) + '->NULL'

# Test case 1: 4->7->5->6->3->2->1->NULL
list1 = ListNode(4)
list1.next = ListNode(7)
list1.next.next = ListNode(5)
list1.next.next.next = ListNode(6)
list1.next.next.next.next = ListNode(3)
list1.next.next.next.next.next = ListNode(2)
list1.next.next.next.next.next.next = ListNode(1)
print('Example 1:', print_list(odd_even_list(list1)))
# 4->5->3->1->7->6->2->NULL

# Test case 2: 1->2->3->4->5->NULL
list2 = ListNode(1)
list2.next = ListNode(2)
list2.next.next = ListNode(3)
list2.next.next.next = ListNode(4)
list2.next.next.next.next = ListNode(5)
print('Example 2:', print_list(odd_even_list(list2)))
# 1->3->5->2->4->NULL

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (More Explicit)

Here's a more explicit version that might be easier to understand:

JavaScript Alternative
Python Alternative

/**
 * Alternative: More explicit version
 */
function oddEvenListExplicit(head) {
  if (!head || !head.next) {
    return head;
  }
  
  const oddHead = head;
  const evenHead = head.next;
  
  let odd = oddHead;
  let even = evenHead;
  
  // Traverse and build odd and even lists
  while (even && even.next) {
    // Next odd node is two steps ahead
    odd.next = even.next;
    odd = odd.next;
    
    // Next even node is two steps ahead from current even
    even.next = odd.next;
    even = even.next;
  }
  
  // Connect odd list to even list
  odd.next = evenHead;
  
  return oddHead;
}

def odd_even_list_explicit(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Alternative: More explicit version
    """
    if not head or not head.next:
        return head
    
    odd_head = head
    even_head = head.next
    
    odd = odd_head
    even = even_head
    
    # Traverse and build odd and even lists
    while even and even.next:
        # Next odd node is two steps ahead
        odd.next = even.next
        odd = odd.next
        
        # Next even node is two steps ahead from current even
        even.next = odd.next
        even = even.next
    
    # Connect odd list to even list
    odd.next = even_head
    
    return odd_head

Complexity

Time Complexity: O(n) - Where n is the number of nodes. We traverse the list once.
Space Complexity: O(1) - We only use a constant amount of extra space (a few pointers).

Approach

The solution uses two-pointer technique to separate and reconnect:

Initialize pointers:
- odd: Points to the last node in the odd list
- even: Points to the last node in the even list
- evenHead: Saves the head of the even list
Traverse and split:
- While even and even.next exist:
  - Link next odd node: odd.next = even.next
  - Move odd pointer forward
  - Link next even node: even.next = odd.next
  - Move even pointer forward
Connect lists:
- Link the end of odd list to the head of even list: odd.next = evenHead
Return: Return the original head (which is now the head of odd list)

Key Insights

Two-pointer technique: Use separate pointers for odd and even positions
In-place modification: Reorder without creating new nodes
Save even head: Need to remember where even list starts
Skip by two: Move two steps at a time to alternate positions
O(1) space: Only use pointers, no extra data structures

Step-by-Step Example

Let's trace through Example 2: 1->2->3->4->5->NULL

Initial:
  1->2->3->4->5->NULL
  ↑  ↑
 odd even

Step 1:
  odd.next = even.next → odd.next = 3
  1->3  2->3->4->5->NULL
  ↑     ↑
 odd   even
  
  odd = odd.next → odd points to 3
  1->3->4->5->NULL, 2->3->4->5->NULL
     ↑  ↑
    odd even
  
  even.next = odd.next → even.next = 4
  1->3->4->5->NULL, 2->4->5->NULL
     ↑  ↑
    odd even
  
  even = even.next → even points to 4
  1->3->4->5->NULL, 2->4->5->NULL
     ↑     ↑
    odd   even

Step 2:
  odd.next = even.next → odd.next = 5
  1->3->5->NULL, 2->4->5->NULL
     ↑     ↑
    odd   even
  
  odd = odd.next → odd points to 5
  1->3->5->NULL, 2->4->5->NULL
        ↑  ↑
       odd even
  
  even.next = odd.next → even.next = null
  1->3->5->NULL, 2->4->NULL
        ↑  ↑
       odd even
  
  even = even.next → even = null
  Loop ends (even is null)

Final: Connect odd list to even list
  odd.next = evenHead → odd.next = 2
  1->3->5->2->4->NULL

Result: 1->3->5->2->4->NULL

Visual Representation

Original:    1->2->3->4->5->NULL
Positions:   1  2  3  4  5

Split:
Odd list:    1->3->5->NULL
Even list:   2->4->NULL

Connect:
Result:      1->3->5->2->4->NULL

Edge Cases

Empty list: Return null
Single node: Return the node as-is
Two nodes: Swap positions (1->2 becomes 1->2, which is correct)
Odd length: Works correctly
Even length: Works correctly

Important Notes

1-indexed positions: First node is position 1 (odd), second is position 2 (even)
In-place: Modifies the original list structure
No new nodes: Only rearranges existing nodes
Two pointers: Efficient O(1) space solution
Save even head: Critical to remember where even list starts

Reverse Linked List: Different reordering problem
Reorder List: Reorder list in different pattern
Partition List: Partition by value
Swap Nodes in Pairs: Swap adjacent nodes

Takeaways

Two-pointer technique is efficient for linked list problems
In-place modification saves space
Save head pointers when splitting lists
Skip by two to alternate between odd and even
O(1) space is achievable with careful pointer manipulation

Example(s)​

Solution​

JavaScript Solution

Output:

Python Solution

Output:

Alternative Solution (More Explicit)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (More Explicit)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Related Problems

Takeaways