Split Method of Linked Lists

Question

Hello I am trying to do this:

• split(theList) -given the head reference (theList), splits the linked list in half to create two smaller linked lists. The head reference of the linked list created from the second half of the list is returned. Assume the list contains at least one node. If there is an odd number of nodes in the linked list, the extra node can be placed in either of the two new lists. Your solution must split the list in O(n) time

Here is my code. I want to know if this done in O(n) time?

def split(theList):
  theList = head
  center = head
  index = 0
  while head:
      if index % 2:
          center = center.next
      head = head.next
      index += 1
  headB = center.next
  center.next = None
  return headB

Falko Falko · Accepted Answer · 2015-04-19T16:16:13

Sure, you're basically iterating over all list elements. You're visiting each element exactly once. So the complexity is O(n) with the number of list elements n.

Split Method of Linked Lists

1 Answers