链表的拆分方法

Question

您好，我正在尝试这样做：

• split(theList) - 给定头引用(theList)，将链表分成两半以创建两个较小的链表。返回从列表的后半部分创建的链表的头引用。假设列表包含至少一个节点。如果链表中的节点数为奇数，则可以将多出的节点放入两个新列表中的任一个中。您的解决方案必须在 O(n) 时间内拆分列表

这是我的代码。我想知道这是否在 O(n) 时间内完成？

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

Answer 1

当然，您基本上是在遍历所有列表元素。您恰好访问了每个元素一次。所以复杂度是 O(n) 与列表元素的数量 n.

链表的拆分方法

Split Method of Linked Lists

python

linked-list