Algorithm

Problem Name: 148. Sort List

Given the `head` of a linked list, return the list after sorting it in ascending order.

Example 1:

```Input: head = [4,2,1,3]
Output: [1,2,3,4]
```

Example 2:

```Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
```

Example 3:

```Input: head = []
Output: []
```

Constraints:

• The number of nodes in the list is in the range `[0, 5 * 104]`.
• `-105 <= Node.val <= 105`

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
struct ListNode* divide(struct ListNode *p) {
struct ListNode *a, *b;
a = p;
b = p->next;

while (b) {
b = b->next;        // b moves two steps
if (b) {
a = a->next;    // a moves one steps
b = b->next;
}
}

b = a->next;            // this is the middle point
a->next = NULL;

return b;
}

struct ListNode* merge(struct ListNode *a, struct ListNode *b) {

while (a && b) {
if (a->val  <  b->val) {
c = a;
a = a->next;
} else {
c = b;
b = b->next;
}
p->next = c;
p = c;
}

p->next = a ? a : b;

}
struct ListNode* sortList(struct ListNode* head) {
struct ListNode *p, *a, *b;

p = divide(head);       // divide the list to two

a = sortList(head);     // sort separately
b = sortList(p);

p = merge(a, b);        // and merge them

return p;
}
``````
Copy The Code &

Input

cmd

Output

cmd
[1,2,3,4]

#2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
}
while (secondHalfTail != null && secondHalfTail.next != null) {
secondHalfTail = secondHalfTail.next.next;
}
firstHalfTail.next = null;
return merge(leftHalf, rightHalf);
}

private ListNode merge(ListNode leftHalf, ListNode rightHalf) {
ListNode dummyNode = new ListNode(-1);
ListNode currNode = dummyNode;
while (leftHalf != null || rightHalf != null) {
if (leftHalf != null && rightHalf != null) {
if (leftHalf.val  <  rightHalf.val) {
currNode.next = new ListNode(leftHalf.val);
leftHalf = leftHalf.next;
} else {
currNode.next = new ListNode(rightHalf.val);
rightHalf = rightHalf.next;
}
} else if (leftHalf != null && rightHalf == null) {
currNode.next = new ListNode(leftHalf.val);
leftHalf = leftHalf.next;
} else {
currNode.next = new ListNode(rightHalf.val);
rightHalf = rightHalf.next;
}
currNode = currNode.next;
}
return dummyNode.next;
}
}
``````
Copy The Code &

Input

cmd

Output

cmd
[1,2,3,4]

#3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
}

return;
}
quickSort(slow.next, tail);
}

function swap(node1, node2) {
let tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}

while (fast != tail) {
if (fast.val  < = p) {
slow = slow.next;
swap(slow, fast);
}
fast = fast.next;
}
return slow;
}
``````
Copy The Code &

Input

cmd

Output

cmd
[-1,0,3,4,5]

#4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
ls = []
ls .sort()
root = head = ListNode(ls[0]) if ls else []
for i in range(1, len(ls)):
return root
``````
Copy The Code &

Input

cmd

Output

cmd
[-1,0,3,4,5]

#5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0148_SortList
{
{

while (fast != null && fast.next != null)
{
prev = slow;
slow = slow.next;
fast = fast.next.next;
}

prev.next = null;

var right = SortList(slow);

return Merge(left, right);
}

private ListNode Merge(ListNode left, ListNode right)
{
var dummy = new ListNode();
var current = dummy;

while (left != null && right != null)
{
if (left.val  <  right.val)
{
current.next = left;
left = left.next;
}
else
{
current.next = right;
right = right.next;
}

current = current.next;
}

if (left != null) current.next = left;
if (right != null) current.next = right;

return dummy.next;
}
}
}
``````
Copy The Code &

Input

cmd