21. 合并两个有序链表(Swift版)

一、题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：

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

二、解题

使用while循环，遍历l1和l2,同时添加一个指针(next)用于创建新的链表(header)。
在循环中指针在l1和l2上移动。
1.当p1和p2都存在是，p1.val > p2.val时，将p2添加到header中，并移动p2，反之将p1添加到header中，并移动p2。最后移动header的next。
2.接下来就是剩下的p1或者p2，当只剩p1时，将p1添加到header中，当只剩p2时，将p2添加到header中。因为剩下的p1或者p2一定是有序的，所以可以直接返回header.next。
时间复杂度为O(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