题目链接

牛客网
LeetCode

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

25. 合并两个排序的链表 - 图1

  1. 示例：
  2. 输入：
  3. {1,3,5},{2,4,6}
  4. 输出：
  5. {1,2,3,4,5,6}

解题思路

方法一：迭代

初始化：定义cur指向新链表的头结点
操作：

  1. 如果l1指向的结点值小于等于l2指向的结点值，则将l1指向的结点值链接到cur的next指针，然后l1指向下一个结点值
  2. 否则，让l2指向下一个结点值
  3. 循环步骤1,2，直到l1或者l2为nullptr
  4. 将l1或者l2剩下的部分链接到cur的后面

    技巧

    一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱结点。
    25. 合并两个排序的链表 - 图2
  1. /*
  2. struct ListNode {
  3.     int val;
  4.     struct ListNode *next;
  5.     ListNode(int x) :
  6.             val(x), next(NULL) {
  7.     }
  8. };*/
  9. class Solution {
  10. public:
  11.     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
  12.     {
  13.         ListNode* vhead = new ListNode(-1);
  14.         ListNode *cur = vhead;
  15.         while(pHead1&&pHead2){
  16.             if(pHead1->val<=pHead2->val){
  17.                 cur->next = pHead1;
  18.                 pHead1 = pHead1->next;
  19.             }else{
  20.                 cur->next = pHead2;
  21.                 pHead2 = pHead2->next;
  22.             }
  23.             cur = cur->next;
  24.         }
  25.         cur->next = pHead1 ? pHead1 : pHead2;
  26.         return vhead->next;
  27.     }
  28. };
  • 时间复杂度：O(m+n),m，n分别为两个单链表的长度
  • 空间复杂度：O(1)

方法二：递归

方法一的迭代版本，很好理解，代码也好写。但是有必要介绍一下递归版本，可以练习递归代码。
写递归代码，最重要的要明白递归函数的功能。可以不必关心递归函数的具体实现。
比如这个ListNode Merge(ListNode pHead1, ListNode* pHead2)
函数功能：合并两个单链表，返回两个单链表头结点值小的那个节点。

  1. /*
  2. struct ListNode {
  3.     int val;
  4.     struct ListNode *next;
  5.     ListNode(int x) :
  6.             val(x), next(NULL) {
  7.     }
  8. };*/
  9. class Solution {
  10. public:
  11.     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
  12.     {
  13.         if(!pHead1) return pHead2;
  14.         if(!pHead2) return pHead1;
  15.         if(pHead1->val<=pHead2->val){
  16.             pHead1->next = Merge(pHead1->next,pHead2);
  17.             return pHead1;
  18.         }else{
  19.             pHead2->next = Merge(pHead1,pHead2->next);
  20.             return pHead2;
  21.         }
  22.     }
  23. };
  • 时间复杂度：O(m+n)
  • 空间复杂度：O(m+n),每一次递归，递归栈都会保存一个变量，最差情况会保存(m+n)个变量