1

I am trying to sort a singly linked list using bubble sort by manipulating ONLY the pointers, no keys.

The following gets stuck in the for loop and loops infinitely. I don't understand why this is. Can anybody explain to me why the end of the list is not being found?

Node* sort_list(Node* head)
{
    Node * temp;
    Node * curr;
    for(bool didSwap = true; didSwap; ) {
            didSwap = false;
            for(curr = head; curr->next != NULL; curr = curr->next) {
                    if(curr->key > curr->next->key) {
                            temp = curr;
                            curr = curr->next;
                            curr->next = temp;
                            didSwap = true;
                    }
                    cout << curr->next->key << endl;
            }
    }
    return head;

}

If I change the code so that the keys (data) are swapped, then the function works properly but for some reason I am not able make it work by manipulating only pointers.

Improve this question

4 Answers 4

Reset to default
3

Logical Error, you are creating an infinite loop with following code -

temp = curr;
curr = curr->next;
curr->next = temp;

I,e next_of_current is pointing to current, so curr->next will always be curr and never will be NULL;

Next you should use previous pointer to fix your list because your list can be traversed in a single direction. So, Think - If A->B->C->NULL; and you make C and B swap then the new list will still point to A->B and next iteration will be wrong ... because you are not modifying your previous next.

So, another implementation may be -

Node* sort_list(Node* head) {
    Node * curr;
    Node * prev;
    for(bool didSwap = true; didSwap; ) {
        didSwap = false;
        prev = head;
        for(curr = head; curr->next != NULL; curr = curr->next) {
                if(curr->key > curr->next->key) {
                        if (head == curr) {
                            head = curr->next;      
                            curr->next = head->next; 
                            head->next = curr; 
                            prev = head;
                        } else {
                            prev->next = curr->next;
                            curr->next = prev->next->next;
                            prev->next->next = curr
                        }
                        didSwap = true;
                } else if (head != curr) {
                    prev = prev->next;
                } 
                //cout << curr->next->key << endl; // <- this may cause crash if curr->next now points to NULL; (i,e last element)
            }
    }
    return head;
}

Hope this helps, regards.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

You have following problem:

Let you have list with three members: ptr1->ptr2->ptr3. Before swap you have following pointer set: curr=ptr1; curr->next=ptr2; curr->next->next=ptr3. When you perform swap you receive curr=ptr2; curr->next=ptr1; curr->next->next=ptr2.

E.g. you lost ptr3. You need to change code of inner loop with following:

temp = curr;
temp->next = curr->next->next;    // Save ptr3
curr = curr->next;
curr->next = temp;
didSwap = true;
Improve this answer

1 Comment

I think you should probably account for being at the end of the Node list. curr->next->next will crash if you are on the last Node element.
0

The field you want to swap is the value. However, if you swap the node, the next field will change, the question becomes a little more complex, you need keep the next field right. In a word, change value is a simple and good method.

Improve this answer

1 Comment

I am trying to accomplish the sorting WITHOUT changing any values. Only pointers.
0 
node *sorted_list(node *head) {
    node *index1,*index2;
    for(index1=head;index1->next!=NULL;index1=index1->next) {
        for(index2=index1->next;index2!=NULL;index2=index2->next) {
            if(index1->data>index2->data) {
                int temp=index1->data;
                index1->data=index2->data;
                index2->data=temp;
            }
        }
    }
    return head;
}
Improve this answer

1 Comment

Please don't post code only answers. Explain what you are doing to solve the problem. This post could also do with some code formatting

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.