合并有序链表

思路

1. 获取两个有序链表的头节点，并将新链表的头节点和尾节点指向较小的节点
2. 使用while循环比较两个链表的节点大小（比较规则：如果链表A的节点a比链表B的节点b大，那么b = b.next，反之a = a.next），并把较小的节点放到新链表的尾部
3. 如果某个链表中的所有节点都被添加到了新链表中，那么直接将另一个链表剩余的所有节点按序添加到新链表尾部

核心代码：

private func merge(head1: inout Node?, head2: inout Node?) -> Node? {
        if head1 == nil && head2 == nil {
            return nil
        }
        if head1 == nil {
            return head2
        }
        if head2 == nil {
            return head1
        }
        
        var newHead = Node(item: nil, next: nil)
        var newFooter = Node(item: nil, next: nil)
        // 新头节点、尾节点指向两个链表首节点最小的节点
        if (head1?.item ?? "").compare(head2?.item ?? "") == .orderedDescending{
            newHead = head2!
            newFooter = head2!
            head2 = head2?.next
        } else {
            newHead = head1!
            newFooter = head1!
            head1 = head1?.next
        }
        // 循环比较，将两个链表中最小的节点插入新链表的尾部
        while head1?.next != nil && head2?.next != nil {
            if (head1?.item ?? "").compare(head2?.item ?? "") == .orderedDescending{
                newFooter.next = head2!
                newFooter = head2!
                head2 = head2?.next
            } else {
                newFooter.next = head1!
                newFooter = head1!
                head1 = head1?.next
            }
        }
        // 如果其中一个链表的所有元素结束的比较，直接将另一个链表剩余的所有节点按序添加到新链表尾部
        if head1?.next == nil {
            newFooter.next = head2
        } else {
            newFooter.next = head1
        }
        return newHead
    }

demo地址：https://github.com/yangguanghei/studyDateStructure