0

Consider a simple struct:

struct Node{
 int val;
 Node *next;
 Node *freeNode;
};

Now I have to sort a given linked list only using freeNode and the method has to be efficient. I can't make another list and use some kind of sorted-insert there. Nor can use genome or bubble sort. The pointer freeNode of any elem in the list can be pointing to any elem in the list.

Now I have come up with two ideas:

  1. Use freeNode to make a doubly Linked List.

    And do pair comparing, i.e. compare the ith elem with the (i+1)th elem. When I find that two elements need to be swapped, I swap them and then again start from the head of the List.

    This algorithm would be more than O(n) (not sure just guessing). It will take much time.

  2. Another method is that my freeNode points to elem that is smaller than it.

    E.g. if I have 30->6->14->56>Tail, then

    56->freeNode->14
30->freeNode->14
14->freeNode->6
6->freeNode->NULL.

    But again, this doesn't help much, because when I insert 45 or 20 I would have to re-arrange my freeNode pointer. And, again, it would not be a very efficient method.

Any suggestions on this? How to use freeNode to implement a better and efficient method for sorting. Pseudo-code would work, and I'd actually prefer that over real code.

EDIT: You can't use arrays, vectors or anything else. Just the freeNode pointer. Use it in any way you want. Keep it NULL or have it point to elements of your choice.

jogojapan
  • 68,383
  • 11
  • 101
  • 131
DeadCoder
  • 87
  • 1
  • 2
  • 9
  • Please, specify, how do you want to sort the list. You can simply use some conventional method of sorting if you map the list to some kind of vector. – V-X Feb 27 '13 at 06:45
  • Have you tried mergesort, quicksort or any other standard sorting method? – n. m. could be an AI Feb 27 '13 at 06:52
  • Not Familiar with any one,. can you explain ???/ – DeadCoder Feb 27 '13 at 06:58
  • @V-X No vectors. Nothing else.just This FreeNode pointer. You can not use any thing else. – DeadCoder Feb 27 '13 at 06:58
  • 2
    Given the constraints in your last edit, this sounds like a homework question. Is it? – Roger Rowland Feb 27 '13 at 07:26
  • 1
    [Mergesort](http://stackoverflow.com/questions/7685/merge-sort-a-linked-list) the list, and there are only about a thousand samples implementations that do it, one linked with this comment. It is O(NlogN) and plenty-efficient for space needs. It requires no additional pointers (except the temp pointers in the recursive algorithm) and in fact, you don't need the `freeNode` pointer for it either (though using it for a `prev` pointer would make the final algorithm significantly more straight-forward to implement). – WhozCraig Feb 27 '13 at 08:14
  • @roger_rowland constraints mean you want to implement that way, more efficiently. See if things work that way as well. – DeadCoder Feb 27 '13 at 12:41

1 Answers1

2

You could make a binary tree. Use next as your right child pointer and freeNode as your left child pointer. Make the first of the nodes you should sort your root. Then, take the rest of your nodes and "insert" them in your new binary tree.

Edit: Like this:

Your typedef:

typedef struct Node{
 int val;
 struct Node *next;
 struct Node *freeNode;
} NodeT;

Some defines to make this code easier to read:

// Conversions to make this code easier to read.
#define pRight freeNode
#define pLeft  next

Recursive binary tree insertion:

static void BinTreeInsert( NodeT *pRootNode, NodeT *pChildNode );

Edit 2: solution removed when made apparent that this was homework. Figure out out dude!

This solution would be O(n log n) best / average case but O(n2) worst case... If the incoming list is already sorted.

http://en.m.wikipedia.org/wiki/Tree_sort#section_1

c.fogelklou
  • 1,781
  • 1
  • 13
  • 26