###### tags: `Leetcode` `easy` `list` `python` `c++` `Top 100 Liked Questions`

# 21. Merge Two Sorted Lists

## [題目來源:] https://leetcode.com/problems/merge-two-sorted-lists/

## 題目:
You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

## 解題想法:
1. Iterative:
設個起點dummy(0)，dummy的next指向list1、list2中較小者
2. Recursive:
list1、list2誰val小就由誰做頭

## Python:

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        
    def addNode(self,node):
        node = ListNode(node)
        if self.head is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
    
    def printList(self):
        if self.head is None:
            print("no any node")
        else:
            temp = self.head
            while temp:
                if temp.next:
                    #不換行之end= "與逗號的意思"
                    end = "->"
                else:
                    end = "\n"
                print(temp.val,end=end)
                temp = temp.next

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        '''
        #Iterative 迭代
        dummyNode = ListNode(0)
        tail = dummyNode
        
        while list1 and list2:  
            if list1.val <= list2.val:
                tail.next = list1
                list1= list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next
            
        if list1 is None:
            tail.next = list2
        if list2 is None:
            tail.next = list1
            
        return dummyNode.next  
        '''
        #Recursive遞迴
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2
        
list1 = LinkedList()
list1.addNode(1)
list1.addNode(2)
list1.addNode(4)
list1.printList()
list2 = LinkedList()
list2.addNode(1)
list2.addNode(3)
list2.addNode(5)
list2.printList()

result = Solution()
list1.head=result.mergeTwoLists(list1.head,list2.head)
list1.printList()

## C++: Iterative

#include <iostream>
using namespace std;

struct ListNode //預設裡面是public
{
    int val;
    ListNode *next;
    //建構子
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void printList(ListNode *head)
{
    while (head != NULL)
    {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode dummy(0);
        ListNode *tail = &dummy;
        while (list1 && list2)
        {
            if (list1->val < list2->val) //指標要配箭頭
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        if (!list1)
            tail->next = list2;
        if (!list2)
            tail->next = list1;
        return dummy.next; // dummy不是pointer 用.
    }
};

int main()
{
    ListNode *list1 = NULL;
    ListNode *red2 = NULL;
    ListNode *red4 = NULL;

    list1 = new ListNode(1);
    red2 = new ListNode(2);
    red4 = new ListNode(4);
    list1->next = red2;
    red2->next = red4;

    ListNode *list2 = NULL;
    ListNode *blue3 = NULL;
    ListNode *blue4 = NULL;

    list2 = new ListNode(1);
    blue3 = new ListNode(3);
    blue4 = new ListNode(4);
    list2->next = blue3;
    blue3->next = blue4;

    cout << "list1: ";
    printList(list1);
    cout << "list2: ";
    printList(list2);

    Solution res;
    ListNode *ans = NULL;
    ans = res.mergeTwoLists(list1, list2);
    cout << "Merge List: ";
    printList(ans);

    return 0;
}

## C++ Recursive

#include <iostream>
using namespace std;

struct ListNode //預設裡面是public
{
    int val;
    ListNode *next;
    //建構子
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void printList(ListNode *head)
{
    while (head != NULL)
    {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (!list1)
            return list2;
        if (!list2)
            return list1;
        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

int main()
{
    ListNode *list1 = NULL;
    ListNode *red2 = NULL;
    ListNode *red4 = NULL;

    list1 = new ListNode(1);
    red2 = new ListNode(2);
    red4 = new ListNode(4);
    list1->next = red2;
    red2->next = red4;

    ListNode *list2 = NULL;
    ListNode *blue3 = NULL;
    ListNode *blue4 = NULL;

    list2 = new ListNode(1);
    blue3 = new ListNode(3);
    blue4 = new ListNode(4);
    list2->next = blue3;
    blue3->next = blue4;

    cout << "list1: ";
    printList(list1);
    cout << "list2: ";
    printList(list2);

    Solution res;
    ListNode *ans = NULL;
    ans = res.mergeTwoLists(list1, list2);
    cout << "Merge List: ";
    printList(ans);

    return 0;
}