Sorting a linked list of integers?

Question

I have a LinkedList that needs to be sorted (it contains ints), and i don't know how to do that. Can anyone give my the source code to sort an int Linked List?

i tried this code which i found online but it didn't work.

    public void sort(LinkedList sortlist)
{
    //Enter loop only if there are elements in list
    boolean swapped = (head != null);

    // Only continue loop if a swap is made
    while (swapped)
    {
        swapped = false;

        // Maintain pointers
        Node curr = head;
        Node next = curr.link;
        Node prev = null;

        // Cannot swap last element with its next
        while (next != null)
        {
            // swap if items in wrong order
            if (curr.data>next.data)
            {
                // notify loop to do one more pass
                swapped = true;

                // swap elements (swapping head in special case
                if (curr == head)
                {
                    head = next;
                    Node temp = next.link;
                    next.link = curr;
                    curr.link = temp;
                    curr = head;
                }
                else
                {
                    prev.link = curr.link;
                    curr.link = next.link;
                    next.link = curr;
                    curr = next;
                }
            }

            // move to next element
            prev = curr;
            curr = curr.link;
            next = curr.link;
        }
    }
}

score 3 · Accepted Answer · edited May 23 '17 at 11:43

3

There is a C++ implementation of merge sort on linked lists given in this handout for Stanford's CS106B course. It runs in time O(n log n), which is quite good.

For a survey of other approaches, check out this older SO answer on how to sort linked lists. There's no code there, but there are good descriptions of how to adapt existing ideas to work on linked lists.

Hope this helps!

edited May 23 '17 at 11:43

Community

1
1

answered Jan 11 '13 at 03:25

templatetypedef

362,284
104
897
1,065

score 0 · Answer 2 · answered Feb 02 '13 at 07:32

Merge sort and quick sort can be used to sort llink-lists ( average O(n.long)) in place. In addition if your numbers are integers, there is a variation of radix sort which work O(n) and it is in place. So you do not meet to convert the link list to an array.

Here is info for the implementation in STL: http://www.cplusplus.com/reference/list/list/sort/

Sorting a linked list of integers?

2 Answers2