Leetcode: Odd Even Linked List

Odd Even Linked List | LeetCode OJ

As you might have noticed by now, all linked list problems can be solved using pointers. Here we need to use 2 pointers as given below

1. Start with pointers at first and second node
2. hop the first pointer over second by making link from first to third and then moving pointer from first to third node
3. hop the second pointer over first pointer (currently pointed at third node) similarly
4. Keep hopping until the end of list
5. Link the first pointer which is at the end of odd list to the second node which is the start of the even list

Remarks:

1. O(n) time complexity for traversing the list once
2. O(1) space complexity for using 3 pointers

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return []
        p, q, r = head, head.next, head.next
        while q and q.next:
            p.next = q.next
            p = p.next
            q.next = p.next
            q = q.next
        p.next = r
        return head