We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Odd Even Linked List

Difficulty: Medium

Problem Description

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 considered even, and so on. Note that the relative order inside both the even and odd groups should remain as it was in the input.

Key Insights

  • The first node in the linked list is treated as an odd-indexed node.
  • The second node is treated as an even-indexed node.
  • We need to maintain the original relative order of the nodes within the odd and even groups.
  • The solution must be achieved using O(1) extra space complexity and O(n) time complexity.

Space and Time Complexity

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

Solution

To solve the problem, we can utilize two pointers to separate the nodes of the linked list into odd and even indexed nodes. We will traverse the linked list, connecting all odd nodes together and all even nodes together. At the end of the traversal, we will connect the last odd node to the head of the even nodes. The algorithm proceeds as follows:

  1. Initialize two pointers, odd and even, to point to the head of the list and the second node, respectively.
  2. Create a temporary pointer evenHead to keep track of the start of the even indexed nodes.
  3. Iterate through the list, adjusting the next pointers of the odd and even nodes accordingly.
  4. Finally, connect the last odd node to the head of the even nodes and return the modified list starting from the head.

Code Solutions

def oddEvenList(head):
    if not head or not head.next:
        return head
    
    odd = head
    even = head.next
    evenHead = even
    
    while even and even.next:
        odd.next = odd.next.next  # Link the next odd node
        even.next = even.next.next  # Link the next even node
        odd = odd.next  # Move to the next odd node
        even = even.next  # Move to the next even node
    
    odd.next = evenHead  # Connect the last odd node to the head of even nodes
    return head
← Back to All Questions