鏈表思維題:給按照絕對值排序的鏈表排序

題目描述

給你一個鏈表的頭結(jié)點?head?，這個鏈表是根據(jù)結(jié)點的絕對值進行升序排序, 返回重新根據(jù)節(jié)點的值進行升序排序的鏈表。

示例 1：

輸入:?head?=?[0,2,-5,5,10,-10]
輸出:?[-10,-5,0,2,5,10]
解釋:
根據(jù)結(jié)點的值的絕對值排序的鏈表是?[0,2,-5,5,10,-10].
根據(jù)結(jié)點的值排序的鏈表是?[-10,-5,0,2,5,10].

示例 2：

輸入:?head?=?[0,1,2]
輸出:?[0,1,2]
解釋:
這個鏈表已經(jīng)是升序的了。

示例 3：

輸入:?head?=?[1]
輸出:?[1]
解釋:
這個鏈表已經(jīng)是升序的了。

提示：

?鏈表節(jié)點數(shù)的范圍是?[1, 10^5].?-5000 <= Node.val <= 5000?head?是根據(jù)結(jié)點絕對值升序排列好的鏈表.

進階：

?你可以在?O(n)?的時間復(fù)雜度之內(nèi)解決這個問題嗎?

解法

先默認(rèn)第一個點已經(jīng)排序完畢。然后從第二個點開始，遇到值為負(fù)數(shù)的節(jié)點，采用頭插法；非負(fù)數(shù)，則繼續(xù)往下遍歷即可。

時間復(fù)雜度?O(n)。

Python3

#?Definition?for?singly-linked?list.
#?class?ListNode:
#?????def?__init__(self,?val=0,?next=None):
#?????????self.val?=?val
#?????????self.next?=?next
class?Solution:
????def?sortLinkedList(self,?head:?Optional[ListNode])?->?Optional[ListNode]:
????????prev,?curr?=?head,?head.next
????????while?curr:
????????????if?curr.val?0:
????????????????t?=?curr.next
????????????????prev.next?=?t
????????????????curr.next?=?head
????????????????head?=?curr
????????????????curr?=?t
????????????else:
????????????????prev,?curr?=?curr,?curr.next
????????return?head

Java

/**
?*?Definition?for?singly-linked?list.
?*?public?class?ListNode?{
?*?????int?val;
?*?????ListNode?next;
?*?????ListNode()?{}
?*?????ListNode(int?val)?{?this.val?=?val;?}
?*?????ListNode(int?val,?ListNode?next)?{?this.val?=?val;?this.next?=?next;?}
?*?}
?*/
class?Solution?{
????public?ListNode?sortLinkedList(ListNode?head)?{
????????ListNode?prev?=?head,?curr?=?head.next;
????????while?(curr?!=?null)?{
????????????if?(curr.val?0)?{
????????????????ListNode?t?=?curr.next;
????????????????prev.next?=?t;
????????????????curr.next?=?head;
????????????????head?=?curr;
????????????????curr?=?t;
????????????}?else?{
????????????????prev?=?curr;
????????????????curr?=?curr.next;
????????????}
????????}
????????return?head;
????}
}

C++

/**
?*?Definition?for?singly-linked?list.
?*?struct?ListNode?{
?*?????int?val;
?*?????ListNode?*next;
?*?????ListNode()?:?val(0),?next(nullptr)?{}
?*?????ListNode(int?x)?:?val(x),?next(nullptr)?{}
?*?????ListNode(int?x,?ListNode?*next)?:?val(x),?next(next)?{}
?*?};
?*/
class?Solution?{
public:
????ListNode*?sortLinkedList(ListNode*?head)?{
????????ListNode*?prev?=?head;
????????ListNode*?curr?=?head->next;
????????while?(curr)
????????{
????????????if?(curr->val?0)
????????????{
????????????????auto?t?=?curr->next;
????????????????prev->next?=?t;
????????????????curr->next?=?head;
????????????????head?=?curr;
????????????????curr?=?t;
????????????}
????????????else
????????????{
????????????????prev?=?curr;
????????????????curr?=?curr->next;
????????????}
????????}
????????return?head;
????}
};

Go

/**
?*?Definition?for?singly-linked?list.
?*?type?ListNode?struct?{
?*?????Val?int
?*?????Next?*ListNode
?*?}
?*/
func?sortLinkedList(head?*ListNode)?*ListNode?{
????prev,?curr?:=?head,?head.Next
????for?curr?!=?nil?{
????????if?curr.Val?0?{
????????????t?:=?curr.Next
????????????prev.Next?=?t
????????????curr.Next?=?head
????????????head?=?curr
????????????curr?=?t
????????}?else?{
????????????prev,?curr?=?curr,?curr.Next
????????}
????}
????return?head
}

---

推薦閱讀

?MQ 消息積壓問題與解決方案?MQ 消息錯亂問題與解決方案?MQ 消息丟失問題與解決方案?MQ 消息重復(fù)消費問題與解決方案?火山引擎違反 Apache 2.0 許可證：以非法方式重新發(fā)行了 SkyWalking

長按識別下圖二維碼，關(guān)注公眾號「Doocs 開源社區(qū)」，第一時間跟你們分享好玩、實用的技術(shù)文章與業(yè)內(nèi)最新資訊。