Sort a single linked list without allocating new node instances

Question

I am using C#, and I wanted to sort a linked list without using extra memory.

Input: listptr→ 11 → 8 → 2→ 4 → 5
Output: listptr→ 2 → 4 → 5 → 8 → 11

This is my class:

public class SNode
{
    public int data;
    public SNode next;
}

Should I create a new temp variable to store the temp list?

Like SNode temp = new SNode(2,NULL);?

This is a homework assignment.

Why don't you use the built-in [`LinkedList`](http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx) class? — Alvin Wong, Oct 21 '12 at 07:27
What's the question? How to sort? How to allocate memory? Why do you want to allocate memory and in the question you say you want to sort without using extra memory? — Carsten Schütte, Oct 21 '12 at 07:28
In C# (except for `unsafe` code), there is no idea of pointers. Just remember, for `struct` or `primitive types` variables are values, while `class` variables are just references. — Alvin Wong, Oct 21 '12 at 07:32
By the way there is **no** way to perform sorting without using extra memories. There may be lots of algorithms that has memory complexity of `O(1)`, but every single function call, or even a counter in a `for` loop **is** using extra memory. — Alvin Wong, Oct 21 '12 at 07:36
Have a look at http://stackoverflow.com/questions/768095/sorting-a-linked-list and http://stackoverflow.com/questions/3315936/sort-a-single-linked-list. They are close matches for your question. — PHeiberg, Oct 21 '12 at 07:42
This was a homework question - dont know who removed the tag. — user1690002, Oct 21 '12 at 08:02
This is exactly I am looking for. My requirement : Efficient method to sort elements of a linked list(int). Sort must be in-place. Do not dynamically allocate new memory. (Language: Java) — Prathibha, Oct 21 '12 at 08:09
@PHeiberg The tag was depreciated because of the type of questions and answers it was soliciting; they simply weren't what we expect in terms of quality at Stack Exchange. That said, full answers are appropriate, regardless of the declaration of whether or not it is homework. — casperOne, Oct 22 '12 at 11:59

LightStriker · Answer 1 · 2012-10-21T07:34:47.150

Well, one easy way would be to break the chain, sort it in a List<> and then relink the objects.

Here's my take on this. I know I totally fail the "No extra memory." part. Sorry.

public class SNode : IComparable
{
    public int data;
    public SNode next;

    // Implement IComparable, so List.Sort can do its magic.
    public int CompareTo(object obj)
    {
        SNode node = obj as SNode;
        if (node == null)
            throw (new Exception()); // Wrong type?

        if (this.data < node.data)
            return -1;
        else if (this.data > node.data)
            return 1;
        else
            return 0;
    }
}

// Sort the linked nodes.
public SNode Sort(SNode root)
{
    List<SNode> list = Unlink(root);
    list.Sort();
    return Link(list);
}

// Unlink a chained link and return a list of them.
public List<SNode> Unlink(SNode root)
{
    List<SNode> nodes = new List<SNode>();

    nodes.Add(root);
    nodes.AddRange(Unlink(root.next));
    root.next = null;

    return nodes;
}

// Take a list and build a linked list.
public SNode Link(List<SNode> list)
{
    if (list.Count == 0)
        return null;

    for(int i = 0; i < list.Count - 1; i++)
        list[i].next = list[i + 1];

    return list[0];
}

score 0 · Answer 2 · answered Oct 21 '12 at 09:29

One simple (not the most efficient) way would be to create an array with the same size as the list and let each element in the array reference a node. Then you sort the array using the built in sort method. As a final step you loop through the array and set the links for each node to the correct successor.

Since this question is homework, I suspect that you're not allowed to use the built in sort methods. If so, you have to implement any of the existing sorting algorithms for your linked list. Merge sort seems like a good candidate. Here is a good description of the algorithm on a singly linked list.

score 0 · Accepted Answer · answered Oct 21 '12 at 10:41

I should think the point of the exercise is to sort the list in place without creating a copy of the whole thing (so you can presumably use a small amount of memory in the form of variables to help with the sort).

The easiest way to code it is probably to use a bubble sort (although this is horribly inefficient for large lists). The trick is to use a variable to keep track of the node before the current pair, since you will have to adjust its next if you need to swap the order of the nodes in the pair.

As others have pointed out, in a real project you would use the .NET framework to do the heavy lifting for you, but I guess this is a theoretical exercise in pointer manipulation so you're supposed to code it all for yourself.

Sort a single linked list without allocating new node instances

3 Answers3