DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Sort list

#javascript #leetcode #programming #algorithms

Problem statement

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

Problem statement taken from: https://leetcode.com/problems/sort-list

Example 1:

Container

Input: head = [4, 2, 1, 3]
Output: [1, 2, 3, 4]
Enter fullscreen mode Exit fullscreen mode

Example 2:

Container

Input: head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: head = []
Output: []
Enter fullscreen mode Exit fullscreen mode

Constraints:

- The number of nodes in the list is in the range [0, 5 * 10^4].
- -10^5 <= Node.val <= 10^5
Enter fullscreen mode Exit fullscreen mode

Explanation

MergeSort Split and Merge linked list

We can use Merge sort followed by Merge two list algorithm. In short we

  1. Break the list in the middle
  2. Recursively sort the two sub lists
  3. Merge the two sub lists

Let's check the algorithm to understand it better.

Algorithm 

// sortList(head)
- if head == NULL || head->next == NULL
  - return head
- if end

- set temp = NULL
      slow = head
      fast = head

- loop while fast != NULL && fast->next != NULL
  - set temp = slow
        slow = slow->next
        fast = fast->next->next
- while end

- set temp->next = NULL

- l1 = mergeList(head)
  l2 = mergeList(slow)

- return mergeList(l1, l2)

// mergeList(l1, l2)
- set ptr = new ListNode(0)
      current = ptr

- loop while l1 != NULL && l2 != NULL
  - if l1->val <= l2->val
    - current->next = l1
    - l1 = l1->next
  - else
    - current->next = l2
    - l2 = l2->next
  - if end

  - current = current->next
- while end

- if l1 != NULL
  - current->next = l1
  - l1 = l1->next
- if end

- if l2 != NULL
  - current->next = l2
  - l2 = l2->next
- if end

- return ptr->next
Enter fullscreen mode Exit fullscreen mode

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution 

class Solution {
public:
    ListNode* mergelist(ListNode *l1, ListNode *l2) {
        ListNode *ptr = new ListNode(0);
        ListNode *current = ptr;

        while(l1 != NULL && l2 != NULL) {
            if(l1->val <= l2->val) {
                current->next = l1;
                l1 = l1->next;
            } else {
                current->next = l2;
                l2 = l2->next;
            }

            current = current->next;
        }


        if(l1 != NULL) {
            current->next = l1;
            l1 = l1->next;
        }

        if(l2 != NULL) {
            current->next = l2;
            l2 = l2->next;
        }

        return ptr->next;
    }

    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;

        ListNode *temp = NULL;
        ListNode *slow = head;
        ListNode *fast = head;

        while(fast != NULL && fast->next != NULL) {
            temp = slow;
            slow = slow->next;
            fast = fast->next->next;
        }

        temp->next = NULL;

        ListNode* l1 = sortList(head);
        ListNode* l2 = sortList(slow);

        return mergelist(l1, l2);
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution 

func mergeList(l1, l2 *ListNode) *ListNode {
    ptr := &ListNode{0, nil}
    current := ptr

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            current.Next = l1
            l1 = l1.Next
        } else {
            current.Next = l2
            l2 = l2.Next
        }

        current = current.Next
    }

    if l1 != nil {
        current.Next = l1
        l1 = l1.Next
    }

    if l2 != nil {
        current.Next = l2
        l2 = l2.Next
    }

    return ptr.Next
}

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    var temp *ListNode
    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        temp = slow
        slow = slow.Next
        fast = fast.Next.Next
    }

    temp.Next = nil

    l1 := sortList(head)
    l2 := sortList(slow)

    return mergeList(l1, l2)
}
Enter fullscreen mode Exit fullscreen mode

JavaScript solution 

var mergelist = function(l1, l2) {
    let ptr = new ListNode(0);
    let current = ptr;

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

        current = current.next;
    }

    if(l1 != null) {
        current.next = l1;
        l1 = l1.next;
    }

    if(l2 != null) {
        current.next = l2;
        l2 = l2.next;
    }

    return ptr.next;
}

var sortList = function(head) {
    if(head == null || head.next == null) {
        return head;
    }

    let temp = null;
    let slow = head;
    let fast = head;

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

    temp.next = null;

    let l1 = sortList(head);
    let l2 = sortList(slow);

    return mergelist(l1, l2);
};
Enter fullscreen mode Exit fullscreen mode

The time complexity of the approach is O(n * log(n)). The space complexity is O(log(n)).

Let's dry-run our algorithm for a few examples to see how the solution works.

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

// sortList(head)
   head -> 4 -> 2 -> 1 -> 3

Step 1: if head == NULL || head->next == NULL
           head -> 4 and head->next -> 2
           false

Step 2: set temp = NULL
            slow = head
            fast = head
            slow -> 4
            fast -> 4

Step 3: loop while fast != NULL && fast->next != NULL
          fast -> 4 && fast->next -> 2
          true

          temp = slow
          temp -> 4

          slow = slow->next
          slow -> 2

          fast = fast->next->next
          fast -> 1

        loop while fast != NULL && fast->next != NULL
          fast -> 1 && fast-next -> 3
          false

          temp = slow
          temp -> 2

          slow = slow->next
          slow -> 1

          fast = fast->next->next
          fast -> NULL

        loop while fast != NULL && fast->next != NULL
          fast = NULL
          false

Step 4: temp.next = NULL
        temp -> 2

        temp = 4 -> 2 -> NULL

Step 5: l1 = sortList(head)
        head = 4 -> 2 -> NULL

// sortList(head)
   head -> 4 -> 2 -> NULL

Step 6: if head == NULL || head->next == NULL
           head -> 4 and head->next -> 2
           false

Step 7: set temp = NULL
            slow = head
            fast = head
            slow -> 4
            fast -> 4

Step 8: loop while fast != NULL && fast->next != NULL
          fast -> 4 && fast->next -> 2
          true

          temp = slow
          temp -> 4

          slow = slow->next
          slow -> 2

          fast = fast->next->next
          fast -> NULL

        loop while fast != NULL && fast->next != NULL
          fast = NULL
          false

Step 9: temp.next = NULL
        temp -> NULL

        temp = 4 -> NULL

Step 10: l1 = sortList(head)
         head = 4 -> NULL

// sortList(head)
   head -> 4 -> NULL

Step 11: if head == NULL || head->next == NULL
           head -> 4 || head->next -> NULL
           true

           return head

           We rollback to Step 10 and evaluate next line

Step 12:  l2 = sortList(slow)
          slow = 2 -> NULL

// sortList(head)
   head -> 2 -> NULL

Step 13: if head == NULL || head->next == NULL
           head -> 2 || head->next -> NULL
           true

           return head

           We rollback to Step 12 and evaluate next line

Step 14: return mergelist(l1, l2)
            l1 = 4 -> NULL
            l2 = 2 -> NULL

// mergelist(l1, l2)

Step 15: ptr = new ListNode(0)
             = 0 -> NULL

         current = 0 -> NULL

Step 16: loop while l1 != NULL && l2 != NULL
           l1 -> 4
           l2 -> 2
           true

           if l1->val <= l2->val
             4 <= 2
             false
           else
             current->next = l2
             current = 0 -> 2

             l2 = l2->next
             l2 = NULL

           current = current->next
                   = 2 -> NULL

          loop while l1 != NULL && l2 != NULL
            l1 -> 4
            l2 -> NULL
            false

Step 17: if l1 != NULL
            4 != NULL
            true

            current->next = l1
            current = 2 -> 4 -> NULL
            l1 = l1->next
               = NULL

Step 18: if l2 != NULL
            NULL != NULL
            false

Step 19: ptr->next
         ptr = 0 -> 2 -> 4 -> NULL
         ptr->next = 2 -> 4 -> NULL

We follow the algorithm for the rest of the list and return the answer as
1->2->3->4->NULL
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Read next

paharihacker profile image

A Complete Guide to React useEffect vs useLayoutEffect for Beginners

Rajesh Dhiman -

mdarifulhaque profile image

2641. Cousins in Binary Tree II

MD ARIFUL HAQUE -

hitblast profile image

How I configured the Zed editor for daily-driving

HitBlast -

harshboricha98 profile image

Cloud Computing Beyond Containers: How Cloudflare’s Isolates Are Changing the Game

Harsh boricha -