Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the linked list is in the range [0, 104].
• -106 <= Node.val <= 106

Explanation

Alright, imagine you have a line of numbered balls. Some are in odd positions (1st, 3rd, 5th…) and some are in even positions (2nd, 4th, 6th…). You want to rearrange them so all the odd-position balls are first, followed by all the even-position balls, keeping their original order within their groups.

Here’s how you do it step-by-step:

🍡Check for Empty or Short Line:

If there are no balls or only one ball, you’re done! There’s nothing to rearrange.

🍡Separate the Balls:

• Imagine you have two “strings” or lists: one for odd balls and one for even balls.
• The first ball goes on the “odd” string.
• The second ball goes on the “even” string.
• From then on, you keep alternating, putting each ball on the correct string.

🍡Move Along the Line:

• You use two “pointers” (think of them as your fingers) to keep track of where you are on the “odd” and “even” strings.
• You move these pointers along, adding balls to the ends of the respective strings.

🍡Connect the Strings:

• Once you’ve gone through all the balls, take the end of the “odd” string and connect it to the beginning of the “even” string.
• Now you have one long string with all the odd balls first, followed by all the even balls.

🍡You’re Done!

• The balls are rearranged as requested.

Implementation

Python

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

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Handle the case where the list is empty
        if not head:
            return None
        
        # Handle the case where the list has only one node
        if not head.next:
            return head

        # Initialize pointers for the odd and even lists
        odds_head = head  # Head of the odd list
        odds_tail = head  # Tail of the odd list
        evens_head = head.next  # Head of the even list
        evens_tail = head.next  # Tail of the even list

        # Iterate through the list, rearranging the nodes
        while odds_tail.next and evens_tail.next:
            # Connect the current odd node to the next odd node
            odds_tail.next = evens_tail.next
            # Move the odds_tail pointer to the next odd node
            odds_tail = odds_tail.next
            
            # Connect the current even node to the next even node
            evens_tail.next = odds_tail.next
            # Move the evens_tail pointer to the next even node
            evens_tail = evens_tail.next

        # Connect the tail of the odd list to the head of the even list
        odds_tail.next = evens_head
        
        # Return the head of the reordered list (which is the original head)
        return odds_head

Typescript

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

function oddEvenList(head: ListNode | null): ListNode | null {
    // If the list is empty, return null.
    if (!head) {
        return null;
    }

    // If the list has only one node, return the head.
    if (!head.next) {
        return head;
    }

    // Initialize pointers for the odd and even lists.
    let oddsHead: ListNode = head; // Head of the odd list.
    let oddsTail: ListNode = head; // Tail of the odd list.
    let evensHead: ListNode | null = head.next; // Head of the even list.
    let evensTail: ListNode | null = head.next; // Tail of the even list.

    // Iterate through the list, rearranging the nodes.
    while (oddsTail.next && evensTail.next) {
        // Connect the current odd node to the next odd node (which is the next even node).
        oddsTail.next = evensTail.next;
        // Move the oddsTail pointer to the new end of the odd list.
        oddsTail = oddsTail.next;
        // Connect the current even node to the next even node (which is the next odd node, or null).
        evensTail.next = oddsTail.next;
        // Move the evensTail pointer to the new end of the even list.
        evensTail = evensTail.next;
    }

    // Connect the tail of the odd list to the head of the even list.
    oddsTail.next = evensHead;

    // Return the head of the reordered list (which is the original head).
    return oddsHead;
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 * Val int
 * Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    // If the list is empty, return nil.
    if head == nil {
        return nil
    }

    // If the list has only one node, return the head.
    if head.Next == nil {
        return head
    }

    // Initialize pointers for the odd and even lists.
    oddsHead := head        // Head of the odd list.
    oddsTail := head        // Tail of the odd list.
    evensHead := head.Next   // Head of the even list.
    evensTail := head.Next   // Tail of the even list.

    // Iterate through the list, rearranging the nodes.
    for oddsTail.Next != nil && evensTail.Next != nil {
        // Connect the current odd node to the next odd node (which is the next even node).
        oddsTail.Next = evensTail.Next
        // Move the oddsTail pointer to the new end of the odd list.
        oddsTail = oddsTail.Next
        // Connect the current even node to the next even node (which is the next odd node, or nil).
        evensTail.Next = oddsTail.Next
        // Move the evensTail pointer to the new end of the even list.
        evensTail = evensTail.Next
    }

    // Connect the tail of the odd list to the head of the even list.
    oddsTail.Next = evensHead

    // Return the head of the reordered list (which is the original head).
    return oddsHead
}

---

If you liked this content I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.

Muchas gracias!

Follow me for more content like this.

X | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me | Medium

Down below you can find other ways to tip my work.

BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"