[数据结构与算法]剑指 Offer 25. 合并两个排序的链表

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

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

0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

思路：

• 构造一个虚拟头节点，用于最终结果的返回
• 先遍历两条链表的公共长度
• 然后分别接着两条链表之前已遍历到的位置开始继续遍历，目的是为了找出较长的那条链表，遍历其剩余未遍历过的节点
• 返回虚拟头结点的Next节点

时间复杂度：O(M+N)，合并操作需遍历两链表。

空间复杂度：O(1)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil && l2 == nil {
        return nil
    }

    head := &ListNode{Val:0, Next:nil} // 创建虚拟头结点
    cur := head
    for l1 != nil && l2 != nil { // 比较两个有序链表的共同长度
        if l1.Val < l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }

    for l1 != nil {
        cur.Next = l1
        l1 = l1.Next
        cur = cur.Next
    }

     for l2 != nil {
        cur.Next = l2
        l2 = l2.Next
        cur = cur.Next
    }

    return head.Next
}