LeetCode刷题之合并两个有序链表

2024/5/10 今天能见度很高，学校南面是山，北校区建立于湖中，北面是湖公园。放几张近期我拍的照片：

和室友上周周末去学校对面公园散步所拍，正好有人在拍结婚照

一天吃完晚饭回实验室所拍，楼即实验室

五一假期去长乐所拍，那天第一次见到有沙滩的大海，下大雨，沿着沙滩一直走，浪漫至极，一瞬我在想我要死也要死在海边的沙滩边，捡了许多贝壳，还有搁浅的船

湖对岸的天主教堂，福建这边宗教很多，文化颇富，甚喜。

今天下午一点开组会，开到了五点，吃饭、散步、回实验室。看了两集仙剑奇侠传三，听着阿桑的《一直很安静》，敲一行行的字，做题。

1、题目描述

2、逻辑分析

这种类型的题，我考研那段时间做过。大致思路是：令给定的两个链表。一个为A，另一个自然就令其为B，接着建立一个C的空链表。分别用索引从A、B链表中依次取元素，小的排前面，大的排后面。有一种情况就是A和B的长度不相等，那么那个长的链表在另一链表元素全部写进C链表后，再将剩余元素写进去，最后返回C链表即可，当时用的伪代码，所以现在的我不会动手，决计看看题解。

题解表示不允许再建立一个链表，只能在存在的链表上操作，有两种方式，第一种是迭代，另一种是递归，我喜欢抽象的事物，更偏向于递归，先看迭代吧，代码如下：

3、代码演示

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                prev.next = list1;
                list1 = list1.next;
            }else{
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        prev.next = list1 == null ? list2:list1;
        return prehead.next; 
}

（1）其中，使用了一个虚拟头节点 prehead 来简化操作。这个虚拟头节点本身并不包含任何有意义的数据，它仅仅是一个哨兵节点（或称为哑节点、占位节点），用来帮助我们在合并链表时不需要考虑空指针的情况。

（2）在合并过程中，我们维护了一个指针 prev，它始终指向当前已合并部分的最后一个节点。当 list1 和 list2 两个链表中的节点都被遍历完时，prev 将指向合并后链表的最后一个节点。

（3）由于我们使用了 prehead 这个虚拟头节点，因此合并后链表的真正头节点并不是 prev 所指向的节点，而是 prev 的下一个节点，即 prehead.next。这是因为 prev 在循环中始终会向后移动，直到它指向最后一个被合并的节点，而 prehead.next 才是合并后链表的第一个节点。在合并结束后，我们需要返回prehead.next

时间复杂度：O(m+n)，空火箭复杂度：O(1)。

大致逻辑就是以上了，好了，我们来看递归实现。

直接上代码：

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

理解递归就是要理解递归。递归给人的感觉就是一层层揭开神秘面纱，探求幽幽深处。

使用递归需要两点：第一点即我要用递归来做什么；第二点即递归的结束条件是什么。本题中，我们的目的就是将两个有序链表合并成一个有序链表。条件是：我们递归地合并 list1 的剩余部分（即 list1.next）和 list2 的整个链表，并将合并后的结果设置为 list1 的下一个节点。然后返回 list1 作为合并后链表的头节点;list2同理。通过这种方式，我们不断地递归地将两个链表拆分成更小的部分，直到一个链表为空，然后我们将非空链表与空链表（或另一个已排序的链表部分）合并。最终，我们得到一个合并后的已排序链表。

时间复杂度：O(m+n)；空间复杂度：O(m+n)。

说实话，这个题我感觉有点难，引入了链表的指针概念，还有抽象的递归。但是我会坚持下去滴，好累呀，眼睛看的好痛，我去看会电视再学学java项目，GOOD NIGHT！