# 21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

## 思路：

1. 建立新的linked list 去鏈結所有的點。
2.

## 迭代方法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dum = ListNode(None)
        prev = dum
        
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next
            prev = prev.next
        
        if l1 == None:
            prev.next = l2
        elif l2 == None:
            prev.next = l1
        
        return dum.next

## 遞迴方法

class Solution:
	def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

		NewList = ListNode()

		def Merge(NewList,node1,node2):

			if node1 == None and node2 == None:
				return

			if node1 == None and node2 != None:
				return node2

			if node2 == None and node1 != None:
				return node1

			if node1.val <= node2.val:
				NewList = node1
				NewList.next = Merge(NewList, node1.next,node2)

			if node1.val > node2.val:
				NewList = node2
				NewList.next = Merge(NewList, node1,node2.next)

			return NewList

		return Merge(NewList,list1,list2)