Problem statement

https://leetcode.com/problems/odd-even-linked-list/

Solution

Classical Linked Lists problem, where we need to keep several pointers: head0 and head1 for head of odd and even sublists, these ones we do not change. We also keep curr and nnext pointers, which we going to update: curr.next = nnext.next, curr = nnext, nnext = curr.next. We also evaluate number of steps (parity of it) were made to sew lists in the end.

Complexity

Time complexity is O(n), space complexity is O(1), because we did not create new objects, but reconnect already existing.

Code

class Solution:
    def oddEvenList(self, head):
        if not head or not head.next or not head.next.next:   #length <=2
            return head
        
        curr = head0 = head
        nnext = head1 = head.next
        
        steps = 0
        
        while nnext.next:
            curr.next = nnext.next
            curr = nnext
            nnext = curr.next
            steps += 1
            
        if steps % 2 == 1:
            curr.next = nnext.next
            nnext.next = head1
        else:
            curr.next = head1
            
        return head0