Insertion Sort - Linked List

#1

Not able to write the code. Its getting very complex to do insertion sort with singly linked list. Help me to approach the problem and check my code. It’s giving segmentation fault.

#2

hi @anishanand3733, Let me share a simpler approach with you ,
ALGO :-

  1. Create an empty sorted list
  2. Traverse the given list, do following for every node.
    …a) Insert current node (in a sorted way) in the sorted list.
  3. Finally , change the head of given linked list to head of sorted (or result) list.

Now the main question is how to implement 2.( a ) part , so for that

  1. If Linked list is empty then make the node as
    head and return it.
  2. If the value of the node to be inserted is smaller than the value of the head node, then insert the node at the start and make it head.
  3. In a loop, find the appropriate node after which the input node is to be inserted. To find the appropriate node start from the head, keep moving until you reach a node X who’s value is greater than the input node. The node just before X is the appropriate node .
  4. Insert the node after the appropriate node found in step 3.

refer to the code (commented) :- https://ide.codingblocks.com/s/234607

1 Like
#3

Got it. Thanks for your help.