Odd Even Linked List

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

• We are given the head of a singly linked list.
• We need to rearrange the linked list such that all nodes with odd values appear before the nodes with even values while preserving the relative order of odd and even nodes.
• The modified linked list should maintain the original order of odd and even nodes.

2. Analyze the problem: To solve this problem, we can use a two-pointer approach. We'll maintain two pointers, odd and even, to keep track of the current odd and even nodes, respectively. We'll also need two additional pointers, even_head and odd_tail, to remember the heads of the even sublist and the tail of the odd sublist.

3. Design an algorithm: Here is the algorithm to solve the problem:

1. If the input linked list is empty or has only one node, return the head as it is.
2. Initialize four pointers:
   • odd_head and odd_tail to None.
   • even_head and even to None.
3. Iterate through each node in the linked list using a loop:
   • If the node's value is odd (i.e., not divisible by 2):
     • If odd_head is None, set both odd_head and odd_tail to the current node.
     • Otherwise, update the next pointer of odd_tail to the current node, and move odd_tail to the current node.
   • If the node's value is even (i.e., divisible by 2):
     • If even_head is None, set both even_head and even to the current node.
     • Otherwise, update the next pointer of even to the current node, and move even to the current node.
4. After the loop, if odd_head is None (i.e., there were no odd nodes), return even_head as the modified linked list.
5. Otherwise, set the next pointer of odd_tail to even_head to connect the odd and even sublists.
6. If even is not None, set its next pointer to None to terminate the even sublist.
7. Return odd_head as the modified linked list.

4. Explain your approach: The approach involves iterating through the linked list and maintaining two pointers, odd_tail and even, to track the tail of the odd sublist and the current even node, respectively. We also keep track of the head of the even sublist using even_head. We update the pointers as we encounter odd and even nodes, and finally connect the odd and even sublists together.

5. Write clean and readable code:

python

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


def oddEvenList(head):
    if not head or not head.next:
        return head

    odd_head = odd_tail = None
    even_head = even = None

    node = head
    while node:
        if node.val % 2 != 0:
            if odd_head is None:
                odd_head = odd_tail = node
            else:
                odd_tail.next = node
                odd_tail = odd_tail.next
        else:
            if even_head is None:
                even_head = even = node
            else:
                even.next = node
                even = even.next

        node = node.next

    if odd_head is None:
        return even_head

    odd_tail.next = even_head

    if even:
        even.next = None

    return odd_head

6. Test your code: Let's test the code with different test cases to ensure its correctness:

1. Test case with an empty list:

   • Input: head = None
   • Expected output: None

2. Test case with only one node:

   • Input: head = ListNode(1)
   • Expected output: ListNode(1)

3. Test case with a list containing odd and even nodes:

   • Input:

     scss

python

# Test case 1: Empty list
head = None
print(oddEvenList(head))  # Output: None

# Test case 2: List with only one node
head = ListNode(1)
print(oddEvenList(head))  # Output: ListNode(1)

# Test case 3: List with odd and even nodes
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
print(oddEvenList(head))  # Output: ListNode(1) -> ListNode(3) -> ListNode(5) -> ListNode(2) -> ListNode(4)

# Test case 4: List with only even nodes
head = ListNode(2)
head.next = ListNode(4)
head.next.next = ListNode(6)
print(oddEvenList(head))  # Output: ListNode(2) -> ListNode(4) -> ListNode(6)

# Test case 5: List with only odd nodes
head = ListNode(1)
head.next = ListNode(3)
head.next.next = ListNode(5)
print(oddEvenList(head))  # Output: ListNode(1) -> ListNode(3) -> ListNode(5)