Odd Even Linked List - Leetcode Solution

The Odd Even Linked List problem on LeetCode requires us to modify a given singly linked list such that all odd-indexed nodes come before the even-indexed nodes. Specifically, the modified list should have all the nodes at odd positions arranged first, followed by all the nodes at even positions. The nodes are numbered 1, 2, 3, ..., n, where n is the length of the list.

Here's a detailed solution to the problem:

1. Initialize two variables, one to keep track of the odd-node list (oddHead) and the other to keep track of the even-node list (evenHead) as null.
2. Traverse through the given linked list (head) and for each node check if it is at an odd or even position using the node number.
3. If the node is at an odd position, add it to the end of the odd-node list by checking if oddHead is null. If it is null, set oddHead to the current node. Otherwise, link the current node to the end of the odd-node list.
4. If the node is at an even position, add it to the end of the even-node list using the same approach as above.
5. After all the nodes have been traversed, link the end of the odd-node list to the start of the even-node list by checking if oddHead is null. If it is null, return evenHead. Otherwise, link the last node of the odd-node list to the first node of the even-node list and return oddHead.

Here's the implementation of the solution in Python:

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        oddHead = oddTail = None
        evenHead = evenTail = None
        count = 1
        
        while head:
            if count % 2 == 1:
                if not oddHead:
                    oddHead = oddTail = head
                else:
                    oddTail.next = head
                    oddTail = oddTail.next
            else:
                if not evenHead:
                    evenHead = evenTail = head
                else:
                    evenTail.next = head
                    evenTail = evenTail.next
                    
            head = head.next
            count += 1
        
        oddTail.next = evenHead
        evenTail.next = None
        
        return oddHead

In the above code, we first check if the given linked list has less than two nodes and if it does, we return it as is. We then initialize variables oddHead and evenHead to null. We also keep track of the tail nodes of both the odd and even lists, initialized to None. A variable count is also initialized to keep track of the node number, starting from 1. We traverse the given linked list using a while loop, keeping track of the node position using count.

If the current node is at an odd position, we add it to the odd list by checking if oddHead is null. If it is null, we set it to the current node and update the oddTail. Otherwise, we link the current node to the end of the odd list and update the oddTail. If the current node is at an even position, we add it to the even list in the same way.

After traversing all the nodes, we link the end of the odd list to the start of the even list by setting oddTail.next to evenHead. We also set evenTail.next to null to terminate the even list. Finally, we return oddHead as the modified linked list.

1