Google | Telephonic Round | STE role
Anonymous User
519

Delete every other node in a circular linked list.

1->2->1 should become 1-1
1->1 should become 1-1
1-2-3-1 should become 1-3-1
1-2-3-4-1 should become 1-3-1
1-2-3-4-5-1 should become 1-3-5-1

I couldn't clear the interview and feel very stupid for approaching the problem in a naive way. But after interview, I took time to solve it properly and came up with this solution. Let me know if you have any inputs:

class Node(object):
      def __init__(self, val, next=None):
            self.val = val
            self.next = next

def removeNodes(head):
      runner = head
      while runner.next is not head:
            runner.next = runner.next.next
            runner = runner.next
            if runner==head:
                  break
      return head
Comments (1)