Why sorting a Linked List is not working?

userO0Dc1 0
Viewed 36

I have a linked list which is in unsorted order. The problem is that I want to sort the given linked list without the use of Merge Sort algorithm. My basic approach written in code is given below:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 
// head = -1 -> 5 -> 3 -> 4 -> 0
 
var sortList = function(head) {
    if(head === null){
        return null;
    }
    if(head.next === null){
        return head;
    }
    
    sortList(head.next);
    return sortingList(head);
};

function sortingList(head){
    let temp = head;
    let prev = head;
    let curr = head.next;
    while(curr !== null){
        if(temp.val < curr.val){
            break;
        }else{
            prev = curr;
            curr = curr.next;
        }
    }
    if(temp.val > prev.val){
        let temp_list = temp.next;
        temp.next = null;
        let prev_list = prev.next;
        prev.next = temp;
        temp.next = prev_list;
        head = temp_list;
    }
    return head;
}

let head = {
  val: -1,
  next: {
    val: 5,
    next: {
      val: 3,
      next: {
        val: 4,
        next: {
          val: 0,
          next: null
        }
      }
    }
  }
}

console.log(sortList(head));

I have checked many times that when we call sortingList, then It wants to give the desired output but don't know why head is not being updated that point. That's why linked list is loosing many items or nodes.

Expected output should be: -1 -> 0 -> 3 -> 4 -> 5

linked-list sorting javascript
1 Answers

There are two issues:

  • In sortList a recursive call is made to sort the rest of the list (after the first node), but although the potentially new head of that sorted sublist is returned, the caller ignores this value. And so head.next is not modified while sometimes it should have.

  • In sortingList the if condition after the loop -- that checks whether the temp node (the head node) should be moved -- is wrong. For instance, if in your example input you would change val: 3 to val: 4 (creating a duplicate value), the problem becomes apparent. That if condition should check whether the prev node reference was moved in the loop. Only if that is true, the node-move operation should be executed.

Here is your code with those two lines of code corrected:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 
// head = -1 -> 5 -> 3 -> 4 -> 0
 
var sortList = function(head) {
    if(head === null){
        return null;
    }
    if(head.next === null){
        return head;
    }
    
    head.next = sortList(head.next); // Corrected
    return sortingList(head);
};

function sortingList(head){
    let temp = head;
    let prev = head;
    let curr = head.next;
    while(curr !== null){
        if(temp.val < curr.val){
            break;
        }else{
            prev = curr;
            curr = curr.next;
        }
    }
    if(prev !== head){ // Corrected
        let temp_list = temp.next;
        temp.next = null;
        let prev_list = prev.next;
        prev.next = temp;
        temp.next = prev_list;
        head = temp_list;
    }
    return head;
}

let head = {
  val: -1,
  next: {
    val: 5,
    next: {
      val: 3,
      next: {
        val: 4,
        next: {
          val: 0,
          next: null
        }
      }
    }
  }
}

console.log(sortList(head));

trincot0
Related