Leetcode: Odd Even Linked List
1 min readDec 26, 2016
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
- Start with pointers at first and second node
- hop the first pointer over second by making link from first to third and then moving pointer from first to third node
- hop the second pointer over first pointer (currently pointed at third node) similarly
- Keep hopping until the end of list
- 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:
- O(n) time complexity for traversing the list once
- 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