Odd Even Linked List

To achieve the required grouping of nodes with odd and even indices together, you can create two pointers: one pointing to the current odd-indexed node and the other to the current even-indexed node. Then, you iterate through the linked list, rearranging the links to group the odd and even nodes together.

Here’s the step-by-step solution to implement the oddEvenList method:

1. Initialize Pointers: Create two pointers odd and even initialized to the first and second nodes respectively.
2. Iterate through the List: Traverse the linked list, updating the next pointers of the odd and even nodes to skip the next node in the sequence.
3. Link Odd and Even Lists: At the end of the traversal, link the last node of the odd list to the first node of the even list.
4. Return Head: Return the head of the linked list, which remains unchanged.

Here is the implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: if there are fewer than 2 nodes, no rearrangement is needed
        if not head or not head.next:
            return head

        # Initialize pointers for odd and even nodes
        odd = head
        even = head.next
        even_head = even

        # Iterate through the linked list
        while even and even.next:
            # Link odd nodes together
            odd.next = even.next
            odd = odd.next

            # Link even nodes together
            even.next = odd.next
            even = even.next

        # Link the last odd node to the first even node
        odd.next = even_head

        return head

Key Takeaways

• This solution fulfills the requirement of using (O(1)) extra space complexity, as it rearranges the existing links without creating additional data structures.
• The time complexity is (O(n)), as it iterates through the linked list once.
• The solution ensures that the relative order inside both the even and odd groups remains as it was in the input, as required.

=begin

v v 1->2->3->4->5->NULL ^ ^ 4 pointers + 1 pointer for keeping track of the second node that will become the start of the even nodes Complicated it more than necessary

I misunderstood T:O(N) O(N) + O(N)

Two Pointers

• odd (creates the odd list)
• even (creates the even list)

1->2->3->4->5->NULL ^ odd.next = odd.next.next 1->3 even.next = even.next.next 2->4

odd.next = even_head

end of the odd list needs to point to the beginning of the even list do this after the loop

odd: ->5 even First time traversal, hop from 1, 3, 5 Odd pointer starts from odd Even pointer starts from 1 tail pointer to keep track

terminating condition

• odd.next is null when I reach the end of the list (odd number of elements)
• even.next is null when I reach the end of the list (even number of elements)

1
2
3
4
5

while !odd.next.nil? || !even.next.nil?
  odd.next = odd.next.next     1->3
  even.next = even.next.next   2->4
end
odd.next = even_head

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {ListNode}
def odd_even_list(head)
  if head.nil?
      return head
  end
  odd = head
  even = odd.next
  even_head = even

# not (A or B) = not A and not B; and
# not (A and B) = not A or not B

    while !(odd.next.nil? || even.next.nil?)
#       create the link for odd list
     odd.next = odd.next.next     
#       traversal for odd list
     odd = odd.next
# create the link for the even list      
     even.next = even.next.next   
#       traversal for the even list
     even = even.next
  end

  odd.next = even_head

  return head
end