How do I sort a linked list?

Question

I have an issue in sorting a linked list. When I use this code the compiler enter an infinite loop and don't do any thing I've been asked to change an insert code to sort code

public void insert(int val) {
    Node currentNode = head;
    Node nextNode = head.next;

    if (currentNode.num > val) {
        Node tmpNode = head;
        head = new Node(val);
        head.next = tmpNode;
        return;
    }

    if (nextNode != null && nextNode.num > val) {
        currentNode.next = new Node(val);
        currentNode.next.next = nextNode;
        return;
    }

    while (nextNode != null && nextNode.num < val) {
        currentNode = nextNode;
        nextNode = nextNode.next;
    }

    currentNode.next = new Node(val);
    currentNode.next.next = nextNode;
}

But that's what I come with it's looks so bad.

This must sort the linked list ... I think !?

public void sort() {
    Node currentNode = head;
    Node nextNode = head.next;
    while (nextNode != null) {
        if (currentNode.num > currentNode.next.num) {
            Node tmpNode = currentNode;
            currentNode.num = currentNode.next.num;
            currentNode.next.num = tmpNode.num;
        }
    }
}

You're never setting `nextNode` in the loop. But even if you would it still wouldn't sort the list. That would just get rid of the infinite loop. — Keiwan, Nov 08 '16 at 18:07
All you've got is a code snippet post, which reeks of low-effort. If you're asking for help understanding, you'll need to provide a better idea of where you're stuck. Add some personal annotations (e.g. code comments) that express what you think the code is doing and people can understand any mistakes in your thinking and help accordingly. — Kache, Nov 08 '16 at 18:13
What do you mean *change an `insert` to a sorting method*? Those are two completely different things. Also, your insert function already keeps the list sorted. (It doesn't check if `head == null` though -just as a sidenote). — Keiwan, Nov 08 '16 at 18:47
that's the main point .... this is the problem that the question very weird — Ahmad M Alaqra, Nov 08 '16 at 18:52
Possible duplicate of [Sorting a linked list in Java](http://stackoverflow.com/questions/8981823/sorting-a-linked-list-in-java) — byxor, Nov 09 '16 at 01:16

score 0 · Answer 1 · edited Apr 07 '21 at 12:09

I assume that you want the linked list to be sorted while insert itself. So that you dont need another function to sort it. You didn't consider the initial scenario where the head will be null only that is the error

public void insert(int val) {
    Node currentNode = head;
    Node nextNode = head.next;

    if (head == null) {
        head = new Node(val);
        head.next = null;
        return;
    }

    if (currentNode.num > val) {
        Node tmpNode = head;
        head = new Node(val);
        head.next = tmpNode;
        return;
    }

    if (nextNode != null && nextNode.num > val) {
        currentNode.next = new Node(val);
        currentNode.next.next = nextNode;
        return;
    }

    while (nextNode != null && nextNode.num < val) {
        currentNode = nextNode;
        nextNode = nextNode.next;
    }

    currentNode.next = new Node(val);
    currentNode.next.next = nextNode;
}

How do I sort a linked list?

1 Answers1