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.

Sort Linked List Already Sorted Using Absolute Values — LeetCode 2046 Python Solution

MediumLeetCode PremiumLinked ListTwo PointersSorting

Problem: #2046
Pattern: Linked List
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

Python

# 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

Complexity

Measure	Complexity
Time	O(n), where n is the length of the linked list
Space	O(1) auxiliary

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.

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.