链表思维题:给按照绝对值排序的链表排序
题目描述
给你一个链表的头结点 head ，这个链表是根据结点的绝对值进行升序排序, 返回重新根据节点的值进行升序排序的链表。
示例 1：
输入: head = [0,2,-5,5,10,-10]
输出: [-10,-5,0,2,5,10]
解释:
根据结点的值的绝对值排序的链表是 [0,2,-5,5,10,-10].
根据结点的值排序的链表是 [-10,-5,0,2,5,10].示例 2：
输入: head = [0,1,2]
输出: [0,1,2]
解释:
这个链表已经是升序的了。示例 3：
输入: head = [1]
输出: [1]
解释:
这个链表已经是升序的了。提示：
•链表节点数的范围是 [1, 10^5].•-5000 <= Node.val <= 5000•head 是根据结点绝对值升序排列好的链表.
进阶：
•你可以在 O(n) 的时间复杂度之内解决这个问题吗?
解法
先默认第一个点已经排序完毕。然后从第二个点开始，遇到值为负数的节点，采用头插法；非负数，则继续往下遍历即可。
时间复杂度 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 headJava
/**
* 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 消息重复消费问题与解决方案•火山引擎违反 Apache 2.0 许可证：以非法方式重新发行了 SkyWalking
长按识别下图二维码，关注公众号「Doocs 开源社区」，第一时间跟你们分享好玩、实用的技术文章与业内最新资讯。
评论