insertion sort in a linked list

Question

I am trying to understand this piece of code which basically performs insertion sort on a linked list. I am lost in this step.

cur->next = prev->next;

What is the role of this step?

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummy = new ListNode();
        ListNode* prev = dummy ;
        ListNode* cur = head ;
        ListNode* next;
        
        while(cur!=NULL){
            next = cur->next ;
            while(prev->next!=NULL && prev->next->val <cur->val){
                prev = prev->next;
            }
            cout<<"prev->next is "<<prev->next<<endl;
            if(prev->next){
                cout<<"val is "<<prev->next->val <<endl;
            }
            cur->next = prev->next;
            prev->next = cur;
            
            prev = dummy ;
            cur = next;
        }
        return dummy->next ;
    }
};

Try drawing it on a paper and it will become clear.

Surt
– Surt

2021-06-25 21:28:21 +00:00
Commented Jun 25, 2021 at 21:28 — Surt
– Surt, Commented Jun 25, 2021 at 21:28

Welbog · Accepted Answer · 2021-06-25 23:36:35Z

1

That and the following line work together to insert cur between prev and prev->next.

cur->next = prev->next;
prev->next = cur;

Before:

prev -------.
            V    
   dummy -> 4 -> 8 -> 10 

cur --------.
            V    
            6 -> 3 -> 16 -> ...
                 ^
next ------------'

After cur->next = prev->next:

prev -------.
            V    
   dummy -> 4 -> 8 -> 10
                 ^
cur --------.   /
            V  /  
            6-/  3 -> 16 -> ...
                 ^
next ------------'

After prev->next = cur and cur = next:

prev -------.
            V    
   dummy -> 4    8 -> 10 
            |    ^
            |   /
            V  /  
            6-/  3 -> 16 -> ...
                 ^
next, cur -------'

So the list is now 4 -> 6 -> 8. next existed to allow the next step to work.

answered Jun 25, 2021 at 23:36

Welbog

60.8k9 gold badges114 silver badges125 bronze badges

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

Collectives™ on Stack Overflow

insertion sort in a linked list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related