原題描述：

?

給定一個單鏈表和數(shù)值x，劃分鏈表使得所有小于x的節(jié)點排在大于等于x的節(jié)點之前。

你應(yīng)該保留兩部分內(nèi)鏈表節(jié)點原有的相對順序。

?

您在真實的面試中是否遇到過這個題？? Yes

?

樣例

給定鏈表?1->4->3->2->5->2->null，并且 x=3

返回?1->2->2->4->3->5->null

?

標簽? 兩根指針?鏈表

?

題目分析：

添加兩個指針，分別指向第一個大于等于X的第一個節(jié)點和小于X的第一個節(jié)點，

實際情況就是第N個節(jié)點大于等于X時，N-1個節(jié)點必然就是小于X；

由于可能節(jié)點第一個值就大于X，此時不存在N-1個節(jié)點，所以在原鏈表前新增一個節(jié)點，用于初始化鏈表循環(huán)。

此時算法復(fù)雜度O(n)。

?

""" Definition of ListNode class ListNode(object):def __init__(self, val, next=None):self.val = valself.next = next """ class Solution:"""@param head: The first node of linked list.@param x: an integer@return: a ListNode"""def partition(self, head, x):# write your code hereif head is None or head.next is None: return headnode = ListNode(-999999)node.next = headhead = nodefollow = headpre = head# 找到第一個值大于x的節(jié)點while follow is not None and follow.val < x:pre = followfollow = follow.next# 所有節(jié)點都小于x，直接返回原h(huán)eadif follow is None: return head.next# 遍歷鏈表,此時pre是follow的上一個節(jié)點while follow.next is not None:if follow.next.val < x:# 刪除原節(jié)點other = follow.nextfollow.next = follow.next.next# 將其值插入到pre之后tmp = pre.nextother.next = tmppre.next = otherpre = pre.nextcontinuefollow = follow.nextreturn head.next

?

轉(zhuǎn)載于:https://www.cnblogs.com/bozhou/p/6945210.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的LintCode Python 简单级题目 96.链表划分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。