LeetCode-in-All
148. Sort List
Medium
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
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Solution
#include <stdio.h>
#include <stdlib.h>
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
// Helper function to create a new ListNode
struct ListNode* createNode(int val) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = val;
node->next = NULL;
return node;
}
// Helper function to merge two sorted linked lists
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy;
struct ListNode* tail = &dummy;
dummy.next = NULL;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if (l1 != NULL) tail->next = l1;
if (l2 != NULL) tail->next = l2;
return dummy.next;
}
// Function to sort the linked list using merge sort
struct ListNode* sortList(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
// Split the list into two halves
struct ListNode *slow = head, *fast = head, *pre = NULL;
while (fast != NULL && fast->next != NULL) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL; // Break the list into two halves
// Recursively sort both halves
struct ListNode* left = sortList(head);
struct ListNode* right = sortList(slow);
// Merge the sorted halves
return merge(left, right);
}