Merge two sorted linked lists

  • + 1 comment

    simple c# code with comments to help you parse it;

    {
    
            //this seems simple, if the lists are sorted, all you need to do is compare each head and insert
            //the smallest one into the new list;
            //the trickiest part of this would be proper node pointer management
            //we need a link to the head of the sorted list and a iterator pointer
            //to make sure we don't lose our place.
            SinglyLinkedListNode sorted = new SinglyLinkedListNode(0);
            SinglyLinkedListNode ind= new SinglyLinkedListNode(0);
            
            //point the sorted list to the first element in the list
            if(head1.data <= head2.data){
                sorted =  head1; //point start of list at it
                ind =  head1; //point iterator at it
                head1 = head1.next; //move head1 pointer over 1
            }
            else{
                sorted = head2; // point start of list at it
                ind = head2; // point iterator at it 
                head2 = head2.next;//move head2 pointer over 1
            }
            
            while( head1 != null || head2!= null)
            {
                if(head1 == null && head2 != null){
                    //continue down head2
                    ind.next = head2;
                    ind = ind.next;
                    head2 = head2.next; //make sure to move head2 over 
                }
                else if(head1 !=null && head2 == null){
                    //head2 is null and we can continue down head1
                    ind.next = head1;
                    ind = ind.next;
                    head1= head1.next; // make sure to move head1 over
                }
                else if(head1.data <= head2.data && ind.next == head1){
                    //head1 is the next lowest number and i next is pointing to it
                    //so we just need to move head1 over 1 as well as i over on same list;
                    head1 = head1.next;
                    ind = ind.next; 
                }
                else if(head1.data <= head2.data && ind.next==head2){
                    //head1 is the next lowest number and i next is not pointing to it
                    //we need to make i next point to head1 then move head1 and iterator over
                    ind.next = head1;
                    head1 =head1.next;
                    ind = ind.next;
                }
                else if(head1.data > head2.data && ind.next== head1){
                    //head2 is the next lowest data and i next is not pointing to it
                    //make i next point to head2 and move head2 and iterator over
                    ind.next = head2;
                    head2 = head2.next;
                    ind = ind.next;
                }
                else{
                    //head2 is next lowest dat and i next is pointing to it
                    //move head2 and iterator over
                    head2 =head2.next;
                    ind = ind.next;
                }
    
            }  
            return sorted;
        }