左神算法学习笔记 - 010【入门】链表入门题目-合并两个有序链表

【算法讲解010【入门】链表入门题目-合并两个有序链表】 https://www.bilibili.com/video/BV1nm4y1W75L/?share_source=copy_web&vd_source=939a5033dc1ec4f712d59a4a4042e169

合并两个有序链表

leetcode

这道题目非常简答，理解链表和对其的调整操作就能理解答案。

但是这里的解法代码先上 labuladong 的版本，他的写法用了头节点技巧，用在链表刷题套路上更好写一点：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        ListNode p1 = list1, p2 = list2;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }

        if (p1 == null) {
            p.next = p2;
        }

        if (p2 == null) {
            p.next = p1;
        }

        return dummy.next;
    }
}

• 我们设置一个虚拟头节点，最终结构返回 dummy.next

• 我们再设置一个和头节点相同的引用 p，他就是在过程中串好所有节点的那个引用

• 题目输入给了两个链表头，我们就设置两个节点 p1 p2 分别对应，来进行遍历

• 跳出循环之后，有一个判空串剩下节点的操作

不过左神在评论区说了：

不推荐设置虚拟头节点的做法！想象这么一个场景，工程上的定义了某种链表节点，初始化函数可能很复杂，并不像刷题中的节点可以随意构造，此时你要怎么办？工程上的节点初始化的时候，内存占用可能很大，并不像刷题中的节点代价那么少，此时你要怎么办？不用假节点，目的是基于这样一种追求：一个结构的事情，就在这个结构自身上做调整，解决这个结构自身的问题，而不是再引入外部的东西。

那么我们看看左神的代码是如何不用虚拟头节点来在「原地」调整好自己的结构得到答案的，以此来学习一下 coding 处理的技巧：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }

        ListNode head = list1.val <= list2.val ? list1 : list2;
        ListNode cur1 = head.next;
        ListNode cur2 = head == list1 ? list2 : list1;
        ListNode pre = head;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }

        pre.next = cur1 != null ? cur1 : cur2;

        return head;
    }
}

• 不用虚拟头节点，最终想返回现有节点的话，就需要判断出 list1 list2 那个是最终头节点，左神解法中 head, cur1, cur2 的三行代码就是做这个事情的。

• 用一个新的 pre 节点去串，这个是一样的

• 另外就是最后循环结束的串联写法上，左神没有用两个 if，而是用三元表达式来决定 pre.next 串哪个节点

这道题的解法就是这样。