合并两个有序链表

01、题目分析

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

示例:

  1. 输入:1->2->4, 1->3->4
  2. 输出:1->1->2->3->4->4


首先我们拿到题目乍眼一看,类似这种链表的合并问题。基本上马上可以想到需要设置一个哨兵节点,这可以在最后让我们比较容易地返回合并后的链表。(不懂哨兵节点的同学,可以先移驾到 06.删除链表倒数第N个节点(19) 进行学习)


假设我们的链表分别为:

l1 = [1,2,4]

l2 = [1,3,4]

同时我们设定一个 “prehead” 的哨兵节点,大概是下面这样:

PNG

02、题目图解

如上图所示,首先我们维护一个 prehead 的哨兵节点。我们其实只需要调整它的 next 指针。让它总是指向l1或者l2中较小的一个,直到l1或者l2任一指向null。这样到了最后,如果l1还是l2中任意一方还有余下元素没有用到,那余下的这些元素一定大于prehead已经合并完的链表(因为是有序链表)。我们只需要将这些元素全部追加到prehead合并完的链表后,最终就得到了我们需要的链表。大概流程如下:

  1. 首先我们将 prehead 指向 l1 或者 l2 中比较小的一个。如果相等,则任意一个都可以。此时的 l1 为 [2,4],l2 为 [1,3,4]

    PNG

  2. 我们继续上面的步骤。将 prehead 的链表指向 l1 和 l2 中较小的一个。现在这里就是指向1。

    PNG

  3. 反复上图步骤。

    PNG

  4. 现在 prehead.Next 就是我们需要的链表。


03、Go语言示例

根据以上分析,我们可以得到下面的题解:

  1. func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
  2. prehead := &ListNode{}
  3. result := prehead
  4. for l1 != nil && l2 != nil {
  5. if l1.Val < l2.Val {
  6. prehead.Next = l1
  7. l1 = l1.Next
  8. }else{
  9. prehead.Next = l2
  10. l2 = l2.Next
  11. }
  12. prehead = prehead.Next
  13. }
  14. if l1 != nil {
  15. prehead.Next = l1
  16. }
  17. if l2 != nil {
  18. prehead.Next = l2
  19. }
  20. return result.Next
  21. }