MediumNo. 2046LeetCode Premium
Sort Linked List Already Sorted Using Absolute Values — LeetCode 2046 Python Solution
- Pattern
- Linked List
- Topics
- Linked List, Two Pointers, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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
- 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].
Python solution
# 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 headComplexity
- Time
- O(n)where n is the length of the linked list
- Space · auxiliary
- O(1)
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0148 | Sort List | Medium |
| 0019 | Remove Nth Node From End of List | Medium |
| 0061 | Rotate List | Medium |
| 0082 | Remove Duplicates from Sorted List II | Medium |
| 0086 | Partition List | Medium |
| 0876 | Middle of the Linked List | Easy |
Frequently asked questions
- How hard is LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values?
LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values?
The Python solution on this page runs in O(n), where n is the length of the linked list.
- What is the space complexity of LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values cover?
LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values is tagged Linked List, Two Pointers and Sorting on LeetCode.
- Is LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values a premium problem?
Yes. LeetCode 2046. Sort Linked List Already Sorted Using Absolute Values is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.