一、題目

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

二、解題

使用while循環(huán)，遍歷l1和l2,同時(shí)添加一個(gè)指針(next)用于創(chuàng)建新的鏈表(header)。
在循環(huán)中指針在l1和l2上移動(dòng)。
1.當(dāng)p1和p2都存在是，p1.val > p2.val時(shí)，將p2添加到header中，并移動(dòng)p2，反之將p1添加到header中，并移動(dòng)p2。最后移動(dòng)header的next。
2.接下來就是剩下的p1或者p2，當(dāng)只剩p1時(shí)，將p1添加到header中，當(dāng)只剩p2時(shí)，將p2添加到header中。因?yàn)槭Ｏ碌膒1或者p2一定是有序的，所以可以直接返回header.next。
時(shí)間復(fù)雜度為O(n)

三、代碼實(shí)現(xiàn)

    class Solution {
        func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
            if l1 == nil || l2 == nil {
                return l1 ?? l2
            }
            var p1 = l1
            var p2 = l2
            let header = ListNode(0)
            var next = header
            while p1 != nil && p2 != nil {
                if p1!.val > p2!.val {
                    next.next = p2
                    p2 = p2?.next
                }else{
                    next.next = p1
                    p1 = p1?.next
                }
                next = next.next!
            }
            if p1 != nil {
                next.next = p1
            }
            if p2 != nil {
                next.next = p2
            }
            return header.next
        }
    }
    
    public class ListNode : CustomStringConvertible{
        public var val: Int
        public var next: ListNode?
        public init(_ val: Int) {
            self.val = val
            self.next = nil
        }
        
        public var description: String {
            var str = "\(val)"
            var next = self
            while next.next != nil{
                str += "->\(next.next!.val)"
                next = next.next!
            }
            return str
        }
    }

Demo地址：github