---
# System prepended metadata

title: 21.Merge Two Sorted Lists
tags: [LeetCode]

---

###### tags: `LeetCode`
21.Merge Two Sorted Lists
===
想法:
兩個Linklist來做為排列，小的先往裡面塞，依此來做排序，最終在把值傳回。

解方:
分別把兩個list設為list1跟list2，然後設定了一個list，來作為排序的繩頭。
這個node擺放上一個指標不跑到HeadNode跟另外一個CurrentNode。

一個while迴圈，condition放l1 and l2。

先行比較l1跟l2值的大小，然後把current先指向小的那一個，然後把list往後遞延。

最後可能會有list沒有被算完的狀況，把current指向剩下的那邊，所以 l1 or l2。

最終return HeadNode.next(Headnode是空的，所以從下一個開始返回)

程式碼如下:
```
# 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 list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """ 
        currentNode = HeadNode = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                currentNode.next = l1
                l1=l1.next
                currentNode=currentNode.next
            else:
                currentNode.next = l2
                l2=l2.next
                currentNode=currentNode.next
        currentNode.next=l1 or l2
        return HeadNode.next

```