Sort LL - DSA Practice | takeUforward

Given the head of a singly linked list. Sort the values of the linked list in non-decreasing order and return the head of the modified linked list.

Example 1:

Input: head -> 5 -> 6 -> 1 -> 2 -> 1

Output: head -> 1 -> 1 -> 2 -> 5 -> 6

Explanation: 1 <= 1 <= 2 <= 5 <= 6

Example 2:

Input: head -> 6 -> 5 -> -1 -> -2 -> -3

Output: head -> -3 -> -2 -> -1 -> 5 -> 6

Explanation: -3 <= -2 <= -1 <= 5 <= 6

Now Your Turn!

Pick the correct output for the given input

Input: head -> -1 -> -2 -> -3 -> -1

head -> -1 -> -1 -> -2 -> -3head -> 1 -> 1 -> 2 -> 3head -> 3 -> 2 -> 1 -> 1head -> -3 -> -2 -> -1 -> -1

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

0 <= number of nodes in the linked list <= 1000
-10⁴ <= ListNode.val <= 10⁴

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Tab-1

1/*
2Definition of singly linked list:
3struct ListNode
4{
5    int val;
6    ListNode *next;
7    ListNode()
8    {
9        val = 0;
10        next = NULL;
11    }
12    ListNode(int data1)
13    {
14        val = data1;
15        next = NULL;
16    }
17    ListNode(int data1, ListNode *next1)
18    {
19        val = data1;
20        next = next1;
21    }
22};
23*/
24 
25class Solution {
26public:
27    ListNode* sortList(ListNode* head) {
28 
29    }
30};
31 
32 

Input:

Nums

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Hint 1

Hint 2

Frequently Occurring Doubts

Why do we need to check for cycles before merging?

Can we remove cycles after merging instead?

Interview Follow-up Questions

What if a cycle exists in the final merged list instead of the child lists?

Can we optimize cycle detection further?