1

How do you sort nodelist by value without using any library.

Example: * Input: 3->1->5->4->2 * Output: 1->2->3->4->5

ListNode.java

import java.util.List;

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

SortLinkList.java

public class SortLinkList {

    public static ListNode sortLinkList(ListNode list) {
        //TODO:
        return list;
    }

}```

2 Answers 2

1

If you want in-place sort you can just implement bubble-sort:

Pseudo-code:

bool notDone = true
while(notDone)
{
    notDone = false;
    cur = head;

    while(cur.nxt != null)
    {
        prev = cur;
        cur = cur.nxt;

        if(cur.val > cur.nxt.val)
        {
            prev.nxt = cur.nxt;
            temp = cur.nxt.nxt;
            cur.nxt.nxt = cur;
            cur.nxt = temp;
            notDone = true;
        }
    }
}
1
  • The concept is right however it doesn't sort the list. Commented Mar 24, 2019 at 9:44
0

1.Make an array of the class which only store each node and for each node, next is pointed to null.Length of the array is no of nodes in the list.

2.Sort the array 3. Link the nodes and return head

PS: why are you using linked list when there is a sorting operation involved , instead of using arrays alone?

3
  • This is algo problem. want to solve without libraries. Commented Mar 24, 2019 at 12:49
  • The solution that is given here does not require any library. I'm assuming you know how to sort (using well known sorting algorithm)an array of objects based on an attribute? Each object being the node of your list. Commented Mar 24, 2019 at 13:25
  • Your assumption is right. This will require extra O(n) space + O(n^2) worst case runtime depending on which sorting you use. This is not something that I am using in my production code. This aas one of the algorithm question. Commented Mar 25, 2019 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.