Trying to Sort a Linked List only by Manipulating Pointers

Question

I am trying to use Selection Sort to sort a Linked list. I can only manipulate the linked lists pointers and not change the keys. I think I have functional logic but, I just return the original unsorted sequence.

bool nodeSwap(Node* head){

  Node* next = head->next;
  if(next == NULL){ return head;}
  head->next = next->next;
  next->next = head;
  head = next;
  return next;
}
Node* sort_list(Node* head){

for(Node* n = head; n->next != NULL; n = n->next){
    for(Node* n1 = head->next; n1 != NULL; n1 = n1->next){
        if(n-> key > n1->key){
            nodeSwap(n);


            }
    }
}
return head;
}

EDIT

Ok so I went through and added more and some logic which actually makes some sense this time and I have my function almost working... Only problem is it always skips sorting over whatever the first two elements are in the list and doesn't return after the sort. Any thoughts on why that might occur?

Node* sort_list(Node* head){

Node* curr;
Node* prev;

  for(curr = head; curr->next != NULL; curr = curr->next){
      if(curr == head){
             head = curr->next;
             curr->next = head->next;
             head->next = curr;
             prev = head;
         }
     else if(curr->key > curr->next->key){
                  head = curr->next;
                  curr->next = head->next;
                  head->next = curr;
                  prev = head;
              } else if(curr -> next -> next != NULL){

                  prev->next = curr->next;
                  curr->next = prev->next->next;
                  prev->next->next = curr;

                  }else if(head != curr){
                        prev = prev->next;
                    }else{}
    }


 return head;
}

You can't swap the two nodes like that. What about the node whose `next` pointer points to the `head` that you pass into `nodeSwap`? — paddy, Oct 24 '13 at 21:53
So you're trying to bubble-sort a linked list, correct ? If you think it is this straight forward, you may wish to think some more. It can be *made* surprisingly simple, but you gotta think deeper. What are you really changing? — WhozCraig, Oct 24 '13 at 22:01

score 0 · Answer 1 · answered Oct 24 '13 at 21:53

0

Try putting code that compiles and/or ask a specific question.

line 3: return head;

in a function which is supposed to return a boolean

answered Oct 24 '13 at 21:53

vincentB

128
1
8

score 0 · Answer 2 · answered Oct 24 '13 at 21:56

0

Seems like you're passing n by value. If you need to modify the value of n inside a function, you need to either make it global (argh) or pass the address of n:

bool nodeSwap(Node** head){
    [...]
}

answered Oct 24 '13 at 21:56

Dan L

325
1
6

score 0 · Answer 3 · answered Oct 24 '13 at 23:00

Single linked list, or double linked list? You mention swapping only data, but you don't provide a pointer definition (key only, or key&data pointers?),

If you want to swap the contents of the two nodes, you need to provide pointers to both nodes in the nodeSwap function,

bool nodeSwap(Node* a, node* b)
{
    if(!a) return false;
    if(!b) return false;
    int temp = a->key;
    a->key = b->key
    b->key = temp;
    void* dtemp = a->data;
    a->data = b->data;
    b->data = dtemp;
    return true;
}

If you want to swap the entire nodes, then you need to provide previous pointers, or go find them (the below assumes a doubly linked list, or where you see 'prev' you go find it),

bool nodeSwap(Node* a, node* b, Node* head)
{
    if(!a) return false;
    if(!b) return false;
    Node* ap=NULL, *bp=NULL;
    //double linked list
    ap = a->prev;
    bp = b->prev;
    //single linked list, get ap (a.previous),
    if( a!=head )
        for( ap=head; ap!=a->next; )
            ap=np->next;
    //single linked list, get bp (b.previous)
    if( b!=head )
        for( bp=head; bp!=b->next; )
            bp=bp->next;
    Node* temp;
    temp = a;
    //fix a->prev->next, b->prev->next
    ap->next = b; //was a
    bp->next = a; //was b
    //swap a->next, b->next
    temp    = a->next;
    a->next = b->next;
    b->next = temp;
    //swap a->prev, b->prev for double-linked list
    temp    = a->prev; //double linked list
    a->prev = b->prev; //double linked list
    b->prev = temp;    //double linked list
    //swap keys, not needed, you moved the Node*
    return true;
}

And here is the nodeSwap with both pointers,

Node* sort_list(Node* head){
    for(Node* n = head; n->next != NULL; n = n->next){
        for(Node* n1 = head->next; n1 != NULL; n1 = n1->next){
            if(n-> key > n1->key){
                nodeSwap(n,n1);
                //nodeSwap(n,n1,head);
            }
        }
    }
    return head;
}

Trying to Sort a Linked List only by Manipulating Pointers

3 Answers3

Linked