Sorting Linked List C++ with pointers

Question

I have been struggling for hours on end with this problem. My goal is to sort a linked list using only pointers (I cannot place linked list into vec or array and then sort). I am given the pointer to the head node of the list. The only methods i can call on the pointers are head->next (next node) and head->key (value of int stored in node, used to make comparisons). I have been using my whiteboard excessively and have tried just about everything I can think of.

Node* sort_list(Node* head)
{
   Node* tempNode = NULL;
   Node* tempHead = head;
   Node* tempNext = head->next;

   while(tempNext!=NULL) {

       if(tempHead->key > tempNext->key) {
           tempNode = tempHead;
           tempHead = tempNext;
           tempNode->next = tempNode->next->next;
           tempHead->next = tempNode;
           tempNext = tempHead->next;
           print_list(tempHead);


        }
        else {  
            tempHead = tempHead->next;
            tempNext = tempNext->next;

        }
    }
    return head;
}

Post the code that you're trying to fix. We're not mind readers - without seeing what you've tried, there is no way to help. — Yuushi
– Yuushi, Commented Oct 25, 2013 at 1:29
What have you tried? Are you looking for someone to write the code for you? — edtheprogrammerguy
– edtheprogrammerguy, Commented Oct 25, 2013 at 1:29
code Sorry, I forgot to paste my code when I made my post. I've tried a lot of things over the past 5 hours. If you critique my code, that would be excellent, but general ideas are helpful too. The method print_list takes in a node and prints out the nodes from that to the end of the list. — dclark
– dclark, Commented Oct 25, 2013 at 1:37
Please add the code to the question, not as a link to an external site in a comment. — Yuushi
– Yuushi, Commented Oct 25, 2013 at 1:40
The code you posted looks more like an attempt at a bubble sort, and it loses track of nodes. You should have tackled the simpler problem of swapping two adjacent elements first. — Beta
– Beta, Commented Oct 25, 2013 at 3:47

ninMonkey · Accepted Answer · 2013-10-25 19:28:34Z

4

Since it's a singly linked list, we can do: (psuedo code)

bool unsorted = true;
while(unsorted) {
    unsorted = false;
    cur = head;         

    while(cur != nullptr) {
        next = cur->next;
        if(next < cur) {
            swap(cur, next)
            unsorted = true;
        }

        cur = cur->next;
    }       
}

edited Oct 25, 2013 at 19:28

answered Oct 25, 2013 at 1:52

ninMonkey

7,5418 gold badges41 silver badges72 bronze badges

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

3 Comments

dclark Over a year ago

I tried you code (pretty sure I did something similar to this a few hours ago). If I input 5 4 3 2 1 to be sorted and return head, it still returns 5 4 3 2 1. code

Mars Over a year ago

@user2113277. The code in your link won't execute the the outer while loop because you have sorted set to false. It goes straight to the end of the code.

MMM Over a year ago

I don't understand people who copy&paste code, modify it arbitrarily and then say "it doesn't work as you say".

Shahroon Farooqi · Accepted Answer · 2018-12-02 17:19:40Z

2

I know its late but I also search for it but didn't get one so I make my own. maybe it will help someone. I am using bubble sort (kind of sort algorithm) to sort data in a single linked list. It just swapping the data inside a node.

void sorting(){
        Node* cur1 = head;
        Node* cur2 = head;

       for (int i = 0; i < getSize(); i++) {
        for (int j = 0; j < getSize() - 1; j++) {
            if (cur1->data < cur2->data) {
                int temp = cur1->data;
                cur1->data = cur2->data;
                cur2->data = temp;

            }
            cur2 = cur2->next;
        }
         cur2 = head;
         cur1 = head->next;
         for (int k = 0; k < i; k++) {
                cur1 = cur1->next;
         }
    }
}

edited Dec 2, 2018 at 17:19

answered Dec 2, 2018 at 17:14

Shahroon Farooqi

1011 silver badge7 bronze badges

1 Comment

Tamim Attafi Over a year ago

Why do you need the third foor-loop? You could just use cur1 = cur1.next;

Dweeberly · Accepted Answer · 2013-10-25 03:24:39Z

Don't feel bad this is a lot harder than it sounds. If this were in an array it would be considerably easier. If the list were doubly linked it would be easier. Take a look at this code, it implements an insertion sort

struct Node {
    int key;
    Node *next;
    } *NodePtr;

// do a simple selection sort http://en.wikipedia.org/wiki/Selection_sort
Node* sort_list(Node* head) {
    Node *top = nullptr; // first Node we will return this value
    Node *current = nullptr;
    bool sorted = false;
    while (sorted == false) {
        // we are going to look for the lowest value in the list
        Node *parent = head;
        Node *lowparent = head; // we need this because list is only linked forward
        Node *low = head; // this will end up with the lowest Node
        sorted = true;
        do {
            // find the lowest valued key
            Node* next = parent->next;
            if (parent->key > next->key) {
                lowparent = parent;
                low = next;
                sorted = false;
                }
            parent = parent->next;
            } while (parent->next != nullptr);
        if (current != nullptr) { // first time current == nullptr
            current->next = low;
            }
        // remove the lowest item from the list and reconnect the list
        // basically you are forming two lists, one with the sorted Nodes 
        // and one with the remaining unsorted Nodes
        current = low;
        if (current == head) { head = current->next; }
        lowparent->next = low->next;
        current->next = nullptr;
        if (top == nullptr) {
            top = current;
            }
        };
    current->next = head;
    return top;
    }

int _tmain(int argc, _TCHAR* argv []) {
    Node nodes[4];
    nodes[0].key = 3;
    nodes[1].key = 4;
    nodes[2].key = 5;
    nodes[3].key = 1;

    nodes[0].next = &nodes[1];
    nodes[1].next = &nodes[2];
    nodes[2].next = &nodes[3];
    nodes[3].next = nullptr;

    auto sortedNodes = sort_list(&nodes[0]);

    return 0;
    }

Sarp Kaya · Accepted Answer · 2013-10-25 05:49:22Z

0

Use a recursive approach as it is the easiest way of dealing with linked structures:

Pseudocode:

SORT(head)
if (head->next == null) 
    return
tempNode = head->next
SORT(tempNode)
if (tempNode->value < head->value) 
    SWAP(head, tempNode)
    SORT(head)
return

so the let's say you have 5 4 3 2 1

1) 5 4 3 1 2

2) 5 4 1 3 2

3) 5 4 1 2 3

4) 5 1 4 2 3

5) 5 1 2 4 3

...

n) 1 2 3 4 5

edited Oct 25, 2013 at 5:49

answered Oct 25, 2013 at 3:58

Sarp Kaya

3,80424 gold badges68 silver badges107 bronze badges

2 Comments

Mars Over a year ago

What is being returned?

Sarp Kaya Over a year ago

It does not return anything, I assumed that SORT is a void type. Hence it does not return anything, as it only swaps values.

Riddance · Accepted Answer · 2013-10-25 07:36:44Z

Assume the Node like this:

struct Node
{
    Node *next;
    int key;
    Node(int x) : key(x), next(NULL) {}
};

use insertion sort algorithm to sort the List:

Node* sort_list(Node* head)
{
    Node dumy_node(0);
    Node *cur_node = head;

    while (cur_node)
    {
        Node *insert_cur_pos =  dumy_node.next;
        Node *insert_pre_pos = NULL;

        while (insert_cur_pos)
        {
            if (insert_cur_pos->key > cur_node->key)
                break;

            insert_pre_pos = insert_cur_pos;
            insert_cur_pos = insert_cur_pos->next;
        }

        if (!insert_pre_pos)
            insert_pre_pos = &dumy_node;

        Node *temp_node = cur_node->next;

        cur_node->next = insert_pre_pos->next;
        insert_pre_pos->next = cur_node;

        cur_node = temp_node;
    }

    return dumy_node.next;
}

ExtraSmart · Accepted Answer · 2014-09-25 18:30:38Z

0

int swapNode( node * &first, node * &second)
 {
    //first we will declare the 
    //previous of the swaping nodes
    node *firstprev=NULL;
    node*secprev=NULL;
    node*current=head;
    //set previous first
    while(current->next!=first)
    {
        current=current->next;
    }
    firstprev=current;
    //seting 2nd previous
    while(current->next!=second)
    {
        current=current->next;
    }

// swap datas, assuming the payload is an int:
int tempdata = first->data;
first->data = second->data;
second->data = tempdata;
//swaping next of the nodes
firstprev->next=second;
secprev->next=first;
}

answered Sep 25, 2014 at 18:30

ExtraSmart

213 bronze badges

Comments

Tokhchukov Aslan · Accepted Answer · 2018-05-17 05:45:18Z

Here is my Merge sort realisation, with O(N*logN) time complexity and constant additional space. Uses C++11

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

typedef pair<ListNode*, ListNode*> PP;

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head==nullptr)return head;
        if (head->next==nullptr) return head;
        if (head->next->next==nullptr){
            if (head->val<=head->next->val){
                return head;
            }
            else {
                ListNode* second=head->next;
                second->next=head;
                head->next=nullptr;
                return second;
            }
        }else {
            PP splitted=split(head);
            return merge(sortList(splitted.first),sortList(splitted.second));
        }
    }

private:  

    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode * head=new ListNode(0);
        ListNode * current=head;
        if (l1==nullptr)return l2;
        if (l2==nullptr)return l1;
        do {
            if (l1->val<=l2->val){
                current->next=l1;
                l1=l1->next;
            }else{
                current->next=l2;
                l2=l2->next;
            }
            current=current->next;
        }while (l1!=nullptr && l2!=nullptr);
        if (l1==nullptr)current->next=l2;
        else current->next=l1;
        return head->next;
    }

    PP split(ListNode* node){
        ListNode* slow=node;
        ListNode* fast=node;
        ListNode* prev;
        while(fast!=nullptr){
            if (fast->next!=nullptr){
                prev=slow;
                slow=slow->next;
                fast=fast->next;
            }else break;
            if(fast->next!=nullptr){
                    fast=fast->next;
                }
            else break;            
        }
        prev->next=nullptr;
        return {node,slow};
    }

};

Christian Schladetsch · Accepted Answer · 2021-08-10 13:00:54Z

0

Use std::list<T>::sort method. Or if you're being precocious, std::forward_list<T>::sort.

Why re-invent the wheel.

answered Aug 10, 2021 at 13:00

Christian Schladetsch

212 bronze badges

Collectives™ on Stack Overflow

Sorting Linked List C++ with pointers

8 Answers 8

3 Comments

1 Comment

Comments

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

3 Comments

1 Comment

Comments

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related