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

ゝ一世哀愁。 2022-11-15 12:59 95阅读 0赞

### 剑指 Offer 22. 链表中倒数第 k 个节点 ###

*  题目难度：简单
 *  方法一：迭代（双指针）
 *  方法二：递归

> 链接：[https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/][https_leetcode-cn.com_problems_he-bing-liang-ge-pai-xu-de-lian-biao-lcof]  
> 来源：力扣（LeetCode）图解算法数据结构

# 题目难度：简单 #

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

示例 1：

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

限制：

0 <= 链表长度 <= 1000

模板

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
    
        }
    }

# 方法一：迭代（双指针） #

解题思路：

*  根据题目描述， 链表  l 1 l1 l1 ,  l 2 l2 l2 是 **递增** 的，因此容易想到使用双指针  l 1 l1 l1 和  l 2 l2 l2 遍历两链表，根据  l 1. v a l l1.val l1.val 和  l 2. v a l l2.val l2.val 的`大小关系`确定节点添加顺序，两节点指针交替前进，直至遍历完毕。
 *  引入伪头节点： 由于初始状态合并链表中无节点，因此循环第一轮时无法将节点添加到合并链表中。
    
     *  解决方案：初始化一个辅助节点  d u m dum dum 作为合并链表的伪头节点，将各节点添加至  d u m dum dum 之后。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]

算法流程：

1.  **初始化**： 伪头节点  d u m dum dum ，节点  c u r cur cur 指向  d u m dum dum 。
2.  **循环合并**： 当  l 1 l1 l1 或  l 2 l2 l2 为空时跳出；
    
    1.  当  l 1. v a l < l 2. v a l l1.val < l2.val l1.val<l2.val 时：  c u r cur cur 的后继节点指定为  l 1 l1 l1 ，并  l 1 l1 l1 向前走一步；
    2.  当  l 1. v a l > = l 2. v a l l1.val >= l2.val l1.val>=l2.val 时：  c u r cur cur 的后继节点指定为  l 2 l2 l2 ，并  l 2 l2 l2 向前走一步；
    3.  节点  c u r cur cur 向前走一步，即  c u r = c u r . n e x t cur = cur.next cur=cur.next 。
3.  **合并剩余尾部**： 跳出时有两种情况，即  l 1 l1 l1 为空 **或**  l 2 l2 l2 为空
    
    1.  若  l 1 ≠ n u l l l l1 \\ne nulll l1=nulll ： 将  l 1 l1 l1 添加至节点  c u r cur cur 之后；
    2.  否则： 将  l 2 l2 l2 添加至节点  c u r cur cur 之后。
4.  **返回值**： 合并链表在伪头节点  d u m dum dum 之后，因此返回  d u m . n e x t dum.next dum.next 即可。

复杂度分析：

*  时间复杂度  O ( M + N ) O(M+N) O(M\+N) ：  M , N M, N M,N 分别为链表  l 1 , l 2 l1,l2 l1,l2 的长度，合并操作需遍历两链表。
 *  空间复杂度  O ( 1 ) O(1) O(1) ： 节点引用  d u m dum dum ,  c u r cur cur 使用常数大小的额外空间。

class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            ListNode dum = new ListNode(-1), cur = dum;
            while(l1 != null && l2 != null) {
        
                if(l1.val < l2.val) {
        
                    cur.next = l1;
                    l1 = l1.next;
                }
                else {
        
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            cur.next = l1 != null ? l1 : l2;
            return dum.next;
        }
    }

# 方法二：递归 #

解题思路：

*  递归内容：如果 `l1` 的 `val` 值更小，则将 `l1.next` 与排序好的链表头相接，`l2` 同理
 *  终止条件：两条链表分别名为 `l1` 和 `l2`，当 `l1` 为空 或 `l2` 为空时结束
 *  返回值：每一层调用都返回排序好的链表头

class Solution {
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
            if(l1 == null) {
        
                return l2;
            }
            if(l2 == null) {
        
                return l1;
            }
    
            if(l1.val < l2.val) {
        
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
        
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }

[https_leetcode-cn.com_problems_he-bing-liang-ge-pai-xu-de-lian-biao-lcof]: https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221022/68d133bddcec40fbb9d9d55ad05e2747.png