Sorting linked list by manipulating pointers

Question

I'm trying to implement Shell sort on a linked list. I divide my original linked list into sub linked list, which contain nodes that have 'k' gap regarding the shell sort algorithm. I want to sort the sub linked list by manipulating the 'next' pointers instead of changing its data field. So I have a sortList function that traverses the linked list and swaps the nodes with swapNodes if it encounters any unordered nodes.

When I pass an unordered linked list with two elements to the sortList I keep loosing one of the nodes in my list. For example, I have 50 and -84 in my list, I pass it to sortList. After the sortList figures that they're unordered it calls swapNodes, but once swapNodes terminates, the resulting list only has 50.

I tried to gdb and found out that when I'm in swapNodes scope the list gets sorted successfully without losing a node, but when it terminates and turns back to sortList scope, both the head and curr points only to 50 and their 'next' field is NULL.

My functions:

void sortList(Node * head, long * n_comp) {
    Node * curr;
    int didSwap = 1;
    while(didSwap) {
        didSwap = 0;
        for(curr = head; curr -> next != NULL; ) {
                *n_comp += 1; //number of comparison
                if(curr->value > curr->next->value) {
                    swapNodes(curr, curr->next, &head);
                    didSwap = 1;
                } 
                curr = curr -> next;
                if (!curr) break;
            }
    }
}

void swapNodes(Node * p1, Node * p2, Node ** start) 
{
    Node *p1pre = NULL;
    Node *p1curr = *start;
    while (p1curr && p1curr!=p1)
    {
        p1pre = p1curr;
        p1curr = p1curr->next;
    }
    Node *p2pre = NULL;
    Node *p2curr = *start;
    while (p2curr && p2curr != p2)
    {
        p2pre = p2curr;
        p2curr = p2curr->next;
    }

    if (p1pre != NULL)
    {
        p1pre->next = p2curr;
    }
    else
    {
        *start = p2curr;
    }
    if (p2pre != NULL)
    {
        p2pre->next = p1curr;
    }
    else
    {
        *start = p1curr;
    }
    Node *temp = p2curr->next;
    p2curr->next = p1curr->next;
    p1curr->next = temp;
    return;
}  
``

sigma1510 sigma1510 · Accepted Answer · 2020-05-02T14:23:59

It's happening for the same reason why you gave start type Node** in the first place: your node [50] is being moved and head moves with it instead of staying at the start of the list. You need to change your sortList method so the parameter head also has type Node**:

void sortList(Node ** head, long * n_comp) {
    Node * curr;
    int didSwap = 1;
    while(didSwap) {
        didSwap = 0;
        for(curr = *head; curr -> next != NULL; ) {
            std::cout<< "It: " << *n_comp<< std::endl;
            *n_comp += 1; //number of comparison
            if(curr->value > curr->next->value) {
                swapNodes(curr, curr->next, head);
                didSwap = 1;
            }
            curr = curr -> next;
            if (!curr) break;
        }
    }
}

Now your head will stay at the start of the list.

Note: this is one of the reasons why sentinel nodes are a thing.

Sorting linked list by manipulating pointers

1 Answers