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) {
struct ListNode head, *p, *c;
p = &head;
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;
return head.next;
}
struct ListNode* sortList(struct ListNode* head) {
struct ListNode *p, *a, *b;
if (!head || !head->next) return head;
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;
}
Input
head = [4,2,1,3]
Output
[1,2,3,4]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode firstHalfTail = head;
ListNode secondHalfHead = head;
ListNode secondHalfTail = head;
while (secondHalfTail != null && secondHalfTail.next != null) {
firstHalfTail = secondHalfHead;
secondHalfHead = secondHalfHead.next;
secondHalfTail = secondHalfTail.next.next;
}
firstHalfTail.next = null;
ListNode leftHalf = sortList(head);
ListNode rightHalf = sortList(secondHalfHead);
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;
}
}
Input
head = [4,2,1,3]
Output
[1,2,3,4]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
function sortList(head) {
quickSort(head, null);
return head;
}
function quickSort(head, tail) {
if (head == tail) {
return;
}
const slow = partition(head, tail);
quickSort(head, slow);
quickSort(slow.next, tail);
}
function swap(node1, node2) {
let tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}
function partition(head, tail) {
let slow = head,
fast = head.next;
let p = head.val;
while (fast != tail) {
if (fast.val < = p) {
slow = slow.next;
swap(slow, fast);
}
fast = fast.next;
}
swap(head, slow);
return slow;
}
Input
head = [-1,5,3,4,0]
Output
[-1,0,3,4,5]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def sortList(self, head):
ls = []
while head: ls.append(head.val); head = head.next
ls .sort()
root = head = ListNode(ls[0]) if ls else []
for i in range(1, len(ls)):
head.next = ListNode(ls[i])
head = head.next
return root
Input
head = [-1,5,3,4,0]
Output
[-1,0,3,4,5]
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0148_SortList
{
public ListNode SortList(ListNode head)
{
if (head == null || head.next == null) return head;
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null)
{
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
var left = SortList(head);
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;
}
}
}
Input
head = []
Output
[]