25.合并两个排序的链表

参考链接

牛客网-剑指offer

帅地

LeetCode

个人尝试（不够精简）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        //todo: l1为空
        if (l1 == null) return l2;
        //todo：l2为空
        if (l2 == null) return l1;

        ListNode pre1 = null, cur1 = l1;
        ListNode pre2 = null, cur2 = l2;
        //以l1为基准，l2小于l1节点时，该节点拼接到l1
        while (cur1 != null && cur2 != null) {
            //l1 > l2
            if (cur1.val > cur2.val) {
                pre2 = cur2;
                cur2 = cur2.next;
                pre2.next = cur1;
                //当pre1 == null且cur1 > cur2，要做拼接时，需要特殊处理
                if (pre1 != null) {
                    pre1.next = pre2;
                    pre1 = pre1.next;
                }
                else {
                    l1 = pre2;
                    pre1 = pre2;
                }
            //l1 <= l2
            } else {
                pre1 = cur1;
                cur1 = cur1.next;
            }
        }
        //l1为空
        if (cur1 == null) pre1.next = cur2;
        //l2为空
        return l1;
    }
}

个人思路：

​ 两个链表各自使用一个pre指针（为了保存上一个节点指针，方便改变上一个节点指针的next指向）、一个cur指针，然后cur1 和 cur2 作比较：

​ 当 cur1 >= cur2 时，pre2 = cur2，cur2 = cur2.next，接着，拼接pre2到pre1的后面

​ 否则（cur1 < cur2），pre1 = cur1，cur1 = cur1.next（cur1继续遍历，直到找到大于cur2）

​ 随后，判空：

​ cur1 先遍历完，将pre1指向cur2，再返回 l1头指针

​ cur2先遍历完，直接返回 l1 头指针

缺点：

​ 对比优秀题解可知，两个pre指针冗余，且使得代码编程会更复杂！！！

优秀题解

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/solutions/1398788/he-bing-liang-ge-pai-xu-de-lian-biao-by-g3z6g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。