LeetCode刷题实战86： 分隔链表
共 2988字，需浏览 6分钟
·
2020-11-07 02:17
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 分隔链表，我们先来看题面：
https://leetcode-cn.com/problems/partition-list/
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
题意
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
解题
题解
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
# 创建两个链表
left = ListNode(0)
right = ListNode(0)
# 以及用来遍历这两个链表的指针
ln = left
rn = right
pnt = head
while pnt is not None:
# 小于x则插入left，否则插入right
if pnt.val < x:
ln.next = ListNode(pnt.val)
ln = ln.next
else:
rn.next = ListNode(pnt.val)
rn = rn.next
pnt = pnt.next
# 将left与right合并
ln.next = right.next
return left.next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
tail = head
if head is None:
return None
# 找到结尾，当找到了大于等于x的元素就放入结尾后面
while tail.next is not None:
tail = tail.next
# 记录遍历的终点
end_point = None
pnt = ListNode(0)
pnt.next = head
head = pnt
while pnt.next is not end_point:
cur = pnt.next
if cur.val >= x:
# 插入在末尾
tail.next = cur
tail = cur
# 如果终点是None的话则进行更新
# end_point只会更新一次
if end_point is None:
end_point = cur
pnt.next = cur.next
continue
pnt = pnt.next
tail.next = None
return head.next
总结
上期推文：