A LeetCode Daily Series — Day 90

Today’s problem is called "Odd Even Linked List"

Updated: at 12:42 AM

In this article, we will tackle the “Odd Even Linked List” problem. This problem is intriguing because it combines the simplicity of linked list operations with the challenge of maintaining specific order constraints. Let’s dive in!

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

Cover Image

Understanding the Problem

Given the head of a singly linked list, our goal is to group all nodes with odd indices together followed by all nodes with even indices, and return the reordered list. The first node is considered odd, the second node is even, and so on. It is crucial to maintain the relative order inside both the even and odd groups as it was in the input list. Additionally, the solution must have O(1) extra space complexity and O(n) time complexity.

Example 1: Example 1

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

Example 2: Example 2

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

Using Efficient Approach (Odd-Even Separation)

To solve this problem efficiently, we can use a two-pointer technique to separate the nodes into odd and even indexed groups. We’ll maintain two pointers, one for odd and one for even, and rearrange the pointers as we traverse the list. Finally, we’ll link the end of the odd list to the head of the even list.

def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return head

    odd, even = head, head.next
    evenHead = even

    while even and even.next:
        odd.next = odd.next.next
        odd = odd.next

        even.next = even.next.next
        even = even.next

    odd.next = evenHead

    return head

Explanation

  1. Initial Checks: If the head is None, we return immediately since there’s nothing to rearrange.
  2. Initialization: We initialize two pointers: odd starting at the head and even starting at the second node (head.next). We also keep a reference to the head of the even list (evenHead).
  3. Reordering:
    • In the while loop, we move the odd pointer to its next odd-indexed node and the even pointer to its next even-indexed node.
    • Specifically, odd.next = odd.next.next moves the odd pointer to skip an even node, and odd = odd.next advances it to the next odd node.
    • Similarly, even.next = even.next.next moves the even pointer to skip an odd node, and even = even.next advances it to the next even node.
  4. Connecting the Sublists: After the loop, we connect the last node in the odd sublist to the head of the even sublist.
  5. Return the Reordered List: Finally, we return the modified list starting from head.

Time Complexity: O(n), The algorithm traverses the list once, thus the time complexity is linear with respect to the number of nodes in the list.

Space Complexity: O(1), The algorithm uses a constant amount of extra space regardless of the size of the input list.

Result

Conclusion

In this article, we discussed the problem of rearranging a singly linked list by grouping all odd-indexed nodes followed by even-indexed nodes. We provided a detailed explanation of an efficient approach to solve this problem using a two-pointer technique.

By understanding this approach, you can tackle similar linked list problems with ease.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series