# 21-Merge Two Sorted Lists
###### tags: `Easy`
## Question
https://leetcode.com/problems/merge-two-sorted-lists/

## Key
先用一個dummy node承接開頭最小的list，以便後面排序，再用一個current node去遍尋merge的過程，過程就是不斷的比較，然後把最current node指向較小的點，直到其中一個list結束，就把另一個list剩下的nodes接起來
## Solution
### C++ recursive solution

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
  {
		// if list1 happen to be NULL
		// we will simply return list2.
		if(l1 == NULL)
        {
			return l2;
		}
		
		// if list2 happen to be NULL
		// we will simply return list1.
		if(l2 == NULL)
        {
			return l1;
		} 
		
		// if value pointend by l1 pointer is less than equal to value pointed by l2 pointer
		// we wall call recursively l1 -> next and whole l2 list.
		if(l1 -> val <= l2 -> val)
        {
			l1 -> next = mergeTwoLists(l1 -> next, l2);
			return l1;
		}
		// we will call recursive l1 whole list and l2 -> next
		else
        {
			l2 -> next = mergeTwoLists(l1, l2 -> next);
			return l2;            
		}
	}
};	

### C++ iterative solution

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
       
	    // if list1 happen to be NULL
		// we will simply return list2.
        if(list1 == NULL)
            return list2;
		
		// if list2 happen to be NULL
		// we will simply return list1.
        if(list2 == NULL)
            return list1;
        //choose which one should be head(smaller one)
        ListNode * ptr = list1;
        if(list1 -> val > list2 -> val)
        {
            ptr = list2;
            list2 = list2 -> next;
        }
        else
        {
            list1 = list1 -> next;
        }
        ListNode *curr = ptr;
        
		// sorting till one of the list doesn't reaches NULL
        while(list1 &&  list2)
        {
            if(list1 -> val < list2 -> val){
                curr->next = list1;
                list1 = list1 -> next;
            }
            else{
                curr->next = list2;
                list2 = list2 -> next;
            }
            curr = curr -> next;
                
        }
		
		// adding remaining elements of bigger list.
        if(!list1)
            curr -> next = list2;
        else
            curr -> next = list1;
            
        return ptr;
       
    }
};

### Python solution

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        
        if not l1:  return l2           #check if linked list1 is empty
        if not l2:  return l1           #check if linked list2 is empty
        
        head=ListNode(0)                
        #creating a head node that will be the head of our list
        cp=head                         
        #A current pointer which will point to the newly created list
        
        while l1 and l2:                
            #iterating through both lists until one/both gets exhausted
            
            if l1.val<l2.val:           
                #if value at list1 is smaller than that of list2
                cp.next=l1
                l1=l1.next
            else:                       
                #checking if value at list2 is less than list1
                cp.next=l2
                l2=l2.next
                
            cp=cp.next                 
            #updating our current pointer
#-------------------END OF WHILE------------------------------------------------------        
        if l1:                          
        #if there are some elements in list1 left
            cp.next=l1
        elif l2:                        
            #if there are some elements in list2 left
            cp.next=l2
#-----------------------------------------------------------------------
        head=head.next                  
    #removing our node with value 0 as it is of no use 
        return head                    
    #returning our head pointer