Sort Linked List Already Sorted Using Absolute Values

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 innon-decreasing order using the actual values of its nodes.

Examples

Example 1:

1
2
3
4
5
6


![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2000-2099/2046.Sort%20Linked%20List%20Already%20Sorted%20Using%20Absolute%20Values/images/image-20211017201240-3.png)
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:

1
2
3
4
5


![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2000-2099/2046.Sort%20Linked%20List%20Already%20Sorted%20Using%20Absolute%20Values/images/image-20211017201318-4.png)
Input: head = [0,1,2]
Output: [0,1,2]
Explanation:
The linked list is already sorted in non-decreasing order.

Example 3:

1
2
3
4


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?

Solution

Method 1 - Two Pointers with Reversal

Intuition: Since the list is sorted by absolute values, negative numbers appear in decreasing order while positive numbers appear in increasing order. We can separate negative and positive nodes, reverse the negative part, and then merge them.

Approach:

Traverse the list and separate negative and non-negative nodes into two separate lists
The negative nodes will be in decreasing order, so reverse that list
Merge the reversed negative list with the non-negative list
This gives us a sorted list by actual values

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


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) {}
};

ListNode* sortLinkedList(ListNode* head) {
    if (!head || !head->next) return head;
    
    // Separate negative and non-negative nodes
    ListNode* negHead = nullptr;
    ListNode* negTail = nullptr;
    ListNode* posHead = nullptr;
    ListNode* posTail = nullptr;
    
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = nullptr;
        
        if (curr->val < 0) {
            if (!negHead) {
                negHead = negTail = curr;
            } else {
                negTail->next = curr;
                negTail = curr;
            }
        } else {
            if (!posHead) {
                posHead = posTail = curr;
            } else {
                posTail->next = curr;
                posTail = curr;
            }
        }
        curr = next;
    }
    
    // Reverse negative list (since they're in decreasing order)
    ListNode* prev = nullptr;
    curr = negHead;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    negHead = prev;
    
    // Merge negative and positive lists
    if (!negHead) return posHead;
    if (!posHead) return negHead;
    
    // Find tail of negative list after reversal
    curr = negHead;
    while (curr->next) {
        curr = curr->next;
    }
    curr->next = posHead;
    
    return negHead;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


type ListNode struct {
    Val  int
    Next *ListNode
}

func sortLinkedList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    var negHead, negTail, posHead, posTail *ListNode
    
    curr := head
    for curr != nil {
        next := curr.Next
        curr.Next = nil
        
        if curr.Val < 0 {
            if negHead == nil {
                negHead = curr
                negTail = curr
            } else {
                negTail.Next = curr
                negTail = curr
            }
        } else {
            if posHead == nil {
                posHead = curr
                posTail = curr
            } else {
                posTail.Next = curr
                posTail = curr
            }
        }
        curr = next
    }
    
    // Reverse negative list
    var prev *ListNode
    curr = negHead
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    negHead = prev
    
    // Merge lists
    if negHead == nil {
        return posHead
    }
    if posHead == nil {
        return negHead
    }
    
    curr = negHead
    for curr.Next != nil {
        curr = curr.Next
    }
    curr.Next = posHead
    
    return negHead
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


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) {
        if (head == null || head.next == null) return head;
        
        ListNode negHead = null, negTail = null;
        ListNode posHead = null, posTail = null;
        
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = null;
            
            if (curr.val < 0) {
                if (negHead == null) {
                    negHead = negTail = curr;
                } else {
                    negTail.next = curr;
                    negTail = curr;
                }
            } else {
                if (posHead == null) {
                    posHead = posTail = curr;
                } else {
                    posTail.next = curr;
                    posTail = curr;
                }
            }
            curr = next;
        }
        
        // Reverse negative list
        ListNode prev = null;
        curr = negHead;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        negHead = prev;
        
        // Merge lists
        if (negHead == null) return posHead;
        if (posHead == null) return negHead;
        
        curr = negHead;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = posHead;
        
        return negHead;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

class Solution {
    fun sortLinkedList(head: ListNode?): ListNode? {
        if (head?.next == null) return head
        
        var negHead: ListNode? = null
        var negTail: ListNode? = null
        var posHead: ListNode? = null
        var posTail: ListNode? = null
        
        var curr = head
        while (curr != null) {
            val next = curr.next
            curr.next = null
            
            if (curr.`val` < 0) {
                if (negHead == null) {
                    negHead = curr
                    negTail = curr
                } else {
                    negTail?.next = curr
                    negTail = curr
                }
            } else {
                if (posHead == null) {
                    posHead = curr
                    posTail = curr
                } else {
                    posTail?.next = curr
                    posTail = curr
                }
            }
            curr = next
        }
        
        // Reverse negative list
        var prev: ListNode? = null
        curr = negHead
        while (curr != null) {
            val next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        }
        negHead = prev
        
        // Merge lists
        if (negHead == null) return posHead
        if (posHead == null) return negHead
        
        curr = negHead
        while (curr?.next != null) {
            curr = curr.next
        }
        curr?.next = posHead
        
        return negHead
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sortLinkedList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    
    neg_head = neg_tail = None
    pos_head = pos_tail = None
    
    curr = head
    while curr:
        next_node = curr.next
        curr.next = None
        
        if curr.val < 0:
            if neg_head is None:
                neg_head = neg_tail = curr
            else:
                neg_tail.next = curr
                neg_tail = curr
        else:
            if pos_head is None:
                pos_head = pos_tail = curr
            else:
                pos_tail.next = curr
                pos_tail = curr
        
        curr = next_node
    
    # Reverse negative list
    prev = None
    curr = neg_head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    neg_head = prev
    
    # Merge lists
    if not neg_head:
        return pos_head
    if not pos_head:
        return neg_head
    
    curr = neg_head
    while curr.next:
        curr = curr.next
    curr.next = pos_head
    
    return neg_head

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

pub fn sort_linked_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return head;
    }
    
    let mut neg_nodes = Vec::new();
    let mut pos_nodes = Vec::new();
    
    let mut curr = head;
    while let Some(mut node) = curr {
        curr = node.next.take();
        
        if node.val < 0 {
            neg_nodes.push(node);
        } else {
            pos_nodes.push(node);
        }
    }
    
    // Reverse negative nodes (they're in decreasing order)
    neg_nodes.reverse();
    
    // Build result list
    let mut result = None;
    let mut tail = &mut result;
    
    // Add negative nodes
    for node in neg_nodes {
        *tail = Some(node);
        tail = &mut tail.as_mut().unwrap().next;
    }
    
    // Add positive nodes
    for node in pos_nodes {
        *tail = Some(node);
        tail = &mut tail.as_mut().unwrap().next;
    }
    
    result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

function sortLinkedList(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return head;
    
    let negHead: ListNode | null = null;
    let negTail: ListNode | null = null;
    let posHead: ListNode | null = null;
    let posTail: ListNode | null = null;
    
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = null;
        
        if (curr.val < 0) {
            if (!negHead) {
                negHead = negTail = curr;
            } else {
                negTail!.next = curr;
                negTail = curr;
            }
        } else {
            if (!posHead) {
                posHead = posTail = curr;
            } else {
                posTail!.next = curr;
                posTail = curr;
            }
        }
        curr = next;
    }
    
    // Reverse negative list
    let prev: ListNode | null = null;
    curr = negHead;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    negHead = prev;
    
    // Merge lists
    if (!negHead) return posHead;
    if (!posHead) return negHead;
    
    curr = negHead;
    while (curr.next) {
        curr = curr.next;
    }
    curr.next = posHead;
    
    return negHead;
}

Complexity

⏰ Time complexity: O(n) where n is the number of nodes (single pass + reversal)
🧺 Space complexity: O(1) excluding the input (only using pointers for manipulation)

Problem#

Examples#

Solution#

Method 1 - Two Pointers with Reversal#

Code#

Complexity#