algoadvance

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(n) time complexity.

Example:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on …

Clarifying Questions

1. Q: Can the list be empty? A: Yes, the list can be empty. Make sure the function handles this case gracefully.

2. Q: Can there be only one node in the list? A: Yes, consider this as a valid scenario and the function should handle it.

3. Q: Should we keep the relative order of odd and even nodes? A: Yes, the relative order should be preserved.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head: ListNode) -> ListNode:
    if not head:
        return None
    
    odd = head
    even = head.next
    even_head = even
    
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    
    odd.next = even_head
    
    return head

Strategy

1. Initialization:
   • If the head is None, return None as there are no nodes to reorder.
   • Initialize two pointers odd and even to point to the first and second nodes respectively. Also, keep a reference to the head of the even list (even_head) because the final merged list will connect after the odd list.
2. Reordering Nodes:
   • Traverse the list using a loop where we separate the nodes into odd and even indexed ones.
   • Update the next pointers to arrange odd and even indices separately.
   • Continue moving the odd and even pointers until no more even nodes or next odd nodes are left.
3. Combining Lists:
   • Connect the end of the odd-indexed list to the head of the even-indexed list stored earlier.

This method ensures that we only traverse the list once (O(n) time complexity), and we don’t use any extra space apart from a few pointers (O(1) space complexity).

Time Complexity

• Time Complexity: O(n) because we traverse the linked list exactly once, where n is the number of nodes in the list.
• Space Complexity: O(1) since we only use pointers to rearrange the nodes in place without using additional space proportional to the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?