Odd Even Linked List

---

Intuition

• This question can be solved naively by keeping two arrays, odd and even, to track which nodes are even and odd, making copies of them, then connecting together and having the last odd node’s next equal to the even node list’s beginning.
• To solve in constant space, we follow logic similar to Reverse Linked List which required a dummy node, except we have two dummy nodes.
• In the end, of traversing, depending on if there are an odd or even number of elements, that is the deciding factor of whether to connect the second to last or last node.
  • Since if there are an odd number of nodes, the last node’s next node must be connected to the 2nd node from the beginning, and if there are an even number of nodes, it must be connected to the first node from the beginning.

Complexity

Runtime

$O(N)$ to traverse through the entire linked list

Space

$O(1)$ to in place link the nodes

Code

Constant Space

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        
        orig_prev, orig_cur = ListNode(-1), ListNode(-1)
        orig_prev.next = orig_cur
        orig_cur.next = head
        prev, cur, itr = orig_prev, orig_cur, head
 
        n = 0
        while itr:
            n += 1
            prev.next = itr
            prev = cur
            cur.next = itr.next
            cur = itr
            itr = itr.next
 
        if n % 2 == 0:
            prev.next = orig_cur.next
        else:
            cur.next = orig_cur.next
            
        return orig_prev.next

Truncated

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        
        orig_prev, orig_cur = ListNode(-1), ListNode(-1)
        orig_prev.next, orig_cur.next = orig_cur, head
        prev, cur, itr = orig_prev, orig_cur, head
 
        n = 0
        while itr:
            n += 1
            prev.next, prev = itr, cur
            cur.next, cur = itr.next, itr
            itr = itr.next
 
        if n % 2 == 0:
            prev.next = orig_cur.next
        else:
            cur.next = orig_cur.next
 
        return orig_prev.next

Naive Approach Without Array

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        if not head.next:
            return head
        
        odd = ListNode(head.val)
        orig_odd = odd
        even = ListNode(head.next.val)
        orig_even = even
 
        itr = head.next.next
        n = 2
        while itr:
            if n % 2 == 0:
                odd.next = ListNode(itr.val)
                odd = odd.next
            else:
                even.next = ListNode(itr.val)
                even = even.next
            itr = itr.next
            n += 1
 
        odd.next = orig_even
        return orig_odd

Naive Approach

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
 
        odd = []
        even = []
        itr = head
        n = 0
        while itr:
            if n % 2 == 0:
                odd.append(ListNode(itr.val))
            else:
                even.append(ListNode(itr.val))
            n += 1
            itr = itr.next
 
        for i in range(1, len(odd)):
            odd[i - 1].next = odd[i]
        for i in range(1, len(even)):
            even[i - 1].next = even[i]
        
        if even:
            odd[-1].next = even[0]
        return odd[0]

Notes

Cards

START Basic Front: Odd Even Linked List Back: Three pointers, two dummies, and keep track of where to connect end to END

---

References

• Odd Even Linked List