Given the head of a singly linked list that is sorted in non-decreasing order using the absolute values of its nodes, return the list sorted in non-decreasing order using the actual values of its nodes.
Example 1:
Input: head = [0,2,-5,5,10,-10]
Output: [-10,-5,0,2,5,10]
Explanation:
The list sorted in non-descending order using the absolute values of the nodes is [0,2,-5,5,10,-10].
The list sorted in non-descending order using the actual values is [-10,-5,0,2,5,10].
Example 2:
Input: head = [0,1,2]
Output: [0,1,2]
Explanation:
The linked list is already sorted in non-decreasing order.
Example 3:
Input: head = [1]
Output: [1]
Explanation:
The linked list is already sorted in non-decreasing order.
Constraints:
The number of nodes in the list is the range [1, 105].
-5000 <= Node.val <= 5000
head is sorted in non-decreasing order using the absolute value of its nodes.
Follow up:
Can you think of a solution with O(n) time complexity?
Solutions
Solution 1: Head Insertion Method
We first assume that the first node is already sorted. Starting from the second node, when we encounter a node with a negative value, we use the head insertion method. For non-negative values, we continue to traverse down.
The time complexity is $O(n)$, where $n$ is the length of the linked list. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9101112131415161718
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defsortLinkedList(self,head:Optional[ListNode])->Optional[ListNode]:prev,curr=head,head.nextwhilecurr:ifcurr.val<0:t=curr.nextprev.next=tcurr.next=headhead=currcurr=telse:prev,curr=curr,curr.nextreturnhead
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcsortLinkedList(head*ListNode)*ListNode{prev,curr:=head,head.Nextforcurr!=nil{ifcurr.Val<0{t:=curr.Nextprev.Next=tcurr.Next=headhead=currcurr=t}else{prev,curr=curr,curr.Next}}returnhead}