超出分区列表问题的时间限制

Question

问题陈述 -

给定一个链表和一个值 x，对其进行分区，以便所有小于 x 的节点都位于大于或等于 x 的节点之前。

应保留两个分区中每个分区中节点的原始相对顺序。

例如

给定 1->4->3->2->5->2 且 x = 3，

返回 1->2->2->4->3->5。

我的代码复杂性是 O(n)，它已经通过了测试，但在提交时，我得到了 TLE。

def partition(self, A, B):
current = A
head = A
prev = None
p1 = None
while(current is not None):
if(current.val < B):
if(p1 is None):
p1 = current
if(prev is not None):
prev.next = current.next
p1.next = A
else:
prev = p1
head = p1
else:
prev.next = current.next
current.next = p1.next
p1.next = current
p1 = current
prev = p1
current = prev.next
else:
prev = current
current = current.next
return head

我也在InterviewBit问题论坛上发布了这个，但没有收到任何回复。

任何人都可以提出任何改进建议。

Answer 1

我正在将prev分配给p1，这对于即使current的位置小于给定元素也不会改变的情况是正确的，但如果它发生了变化，那么我们必须prev移动一步。

最终代码 -

def partition(self, A, B):
current = A
head = A
prev = None
p1 = None
while(current is not None):
if(current.val < B):
if(p1 is None):
p1 = current
if(prev is not None):
prev.next = current.next
p1.next = A
else:
prev = p1
head = p1
else:
prev.next = current.next
current.next = p1.next
p1.next = current
p1 = current
if(prev.next == current):
prev = prev.next
current = prev.next
else:
prev = current
current = current.next
return head