Insertion Sort For A Singly Linked List C++

Question

I am given a head file which defines how the nodes of the linked list are to be created

#ifndef _LISTNODE
#include <cstddef>
#define _LISTNODE

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
#endif

My task is to create a function that will do an insertion sort for a linked list and sort the items in decreasing order (can assume there are no cycles in the linked list.

The function is defined as

ListNode *insertionSortList(ListNode *head)

So my current logic is that I iterate through the linked list until I find that the node that the iterator is currently on is less than the value of the node next to it. In that case, it takes the value of the node that contains the greater number and stores it in a temp pointer. Then my iterator that was on the number that was previous to the node that has just been put into the temp pointer makes it so that this node now points past the node that is breaking the order and to the node after that.

Then I have another iterator go through the list until it finds the spot where it would go to make the order work and then place the node that is being stored with the temp pointer and have the next pointer within this node point to the node that the new iterator has found to be less than it.

I'm sorry if this explanation is a bit messy but it seems to make sense when I draw a diagram out, and I don't see where my code could be breaking this logic, but when I run it with some test cases, it either doesn't sort or sometimes it doesn't sort and doesn't print all the values.

#include <iostream>
#include "ListNode.h"
using namespace std;

ListNode *insertionSortList(ListNode *head)
{
    ListNode *temp;
    for (ListNode *iterator = head; iterator->next != NULL; iterator = iterator->next) //first iterator to find node that breaks the pattern
    {
        if (iterator->val >= iterator->next->val) // if it doesn't break the pattern
        {
            break;
        }

        else //if it does break the pattern
        {
            temp = iterator->next; //store pattern breaking node
            iterator->next = iterator->next->next; //have linked list skip over this pattern breaking node 
            for (ListNode *replacementit = head; replacementit->next != NULL; replacementit = replacementit->next) // find place for patteern breaking node
            {
                if (replacementit->val < temp->val) //if found the right place
                {
                    temp->next = replacementit; //put node into place
                    break;
                }
            }
        }
    }

    return head;
}

int main() //test cases
{
    ListNode A(5);
    ListNode B(6);
    ListNode C(10);
    ListNode D(21);
    ListNode E(25);

    ListNode* head = &A;
    A.next = &B;
    B.next = &C;
    C.next = &D;
    D.next = &E;

    insertionSortList(head);

    for (ListNode *print = head; print->next != NULL; print = print->next) //print out sorted Linked List
    {
        cout << print->val << " ";
    }
}

OUTPUT

5 10 % 

Answer 1

Your implementation is incorrect on the first line inside the first for loop in insertionSortList function.

For example - if the first element of linked list is greater than or equal to the second element of linked list, your code will not execute any more lines in the for loop, it will "break". You can check with list 2 -> 1 -> 3.

Also, at last when you print the linked list, it will always not print the last element because the termination condition is buggy.