?LeetCode刷題實戰(zhàn)86： 分隔鏈表
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從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:
????????# 創(chuàng)建兩個鏈表
????????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
????????
????????# 找到結(jié)尾，當(dāng)找到了大于等于x的元素就放入結(jié)尾后面
????????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的話則進(jìn)行更新
????????????????# end_point只會更新一次
????????????????if?end_point is?None:
????????????????????end_point = cur
????????????????pnt.next = cur.next
????????????????continue
????????????pnt = pnt.next
????????tail.next = None
????????return?head.next
總結(jié)
上期推文：