_2046. Sort Linked List Already Sorted Using Absolute Values.md

2046. Sort Linked List Already Sorted Using Absolute Values

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 04, 2024

Last updated : July 04, 2024

---

Related Topics : Linked List, Two Pointers, Sorting

Acceptance Rate : 66.92 %

---

I decided for simplicity to do the reversal of the negative node order separately than splitting the negatives and positives.

In theory it would have been better to just return tuples of the new negative pointer and new positive pointer but I decided against it to try to aim for a better completion time this time.

Steps that I took:

1. Create dummy heads for the negative and positive chains
2. Iterate through the LinkedList, concatinating the current node to their respective dummy chain (negative or positive values)
3. Reverse the negative chain using a recursive helper
4. Attach the positive head to the end of the newly reversed negative chain
5. Return the head of the negative chain

In the end, this retains a $O(n)$ runtime and $O(1)$ space. It however does make multiple passes (1 pass of ALL, 2 passes of NEGATIVES).

---

Solutions

• m2046 O(n).py

Python

m2046 O(n).py

# 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]:
        # Dummy nodes
        negativeChain = ListNode()
        negativeChainHead = negativeChain

        positiveChain = ListNode()
        positiveChainHead = positiveChain

        curr = head

        while curr :
            if curr.val < 0 :
                negativeChain.next = curr
                negativeChain = curr
            else :
                positiveChain.next = curr
                positiveChain = curr
            curr = curr.next
        positiveChain.next = None
        negativeChain.next = None
        negativeChainHead = negativeChainHead.next
        positiveChainHead = positiveChainHead.next

        # Reverse negatives
        def reverseChain(curr: Optional[ListNode], prev: Optional[ListNode]) -> Optional[ListNode] : # return new head
            output = curr
            if not curr :
                return None
            if curr.next :
                output = reverseChain(curr.next, curr)
            curr.next = prev
            return output
        
        newHead = reverseChain(negativeChainHead, None)

        curr = newHead
        while curr and curr.next :
            curr = curr.next

        if curr :
            curr.next = positiveChainHead
            return newHead
        return positiveChainHead