[数据结构与算法]并两个降序序链表为一个新的降序链表，java实现，时间复杂度O（n），空间复杂度O（1）

package com.zjl.dataStract;

/**
 * @Author: Zjl
 * @Date: 2022/3/14 19:21
 */
public class MergeLinkList {


    public static void main(String[] args) {

        //构造链表1
        Node node1 = new Node(null, 44);
        Node node2 = new Node(node1, 55);
        Node node3 = new Node(node2, 66);
        Node node4 = new Node(node3, 77);
        Node node5 = new Node(node4, 88);
        Node node0 = new Node(node5, 99);

        //构造链表2
        Node node1B = new Node(null, 40);
        Node node2B = new Node(node1B, 50);
        Node node3B = new Node(node2B, 69);
        Node node4B = new Node(node3B, 70);
        Node node5B = new Node(node4B, 90);
        Node node0B = new Node(node5B, 100);

        //合并后的新链表
        Node node = mergeLinList(node0, node0B);

        //输出新链表
        Node p = node;
        while (p != null) {
            System.out.print(p.data + " --> ");
            p = p.next;
        }

    }


    /**
     * 节点结构
     */
    public static class Node {

        public Node(Node next, Integer data) {
            //指针域
            this.next = next;
            //数据域
            this.data = data;
        }

        //指针域
        public Node next;
        //数据域
        public Integer data;

    }

    /**
     * 归并两个降序序链表为一个新的降序链表
     * 时间复杂度O（n），空间复杂度O（1）
     *
     * @param L1 非空 且降序
     * @param L2 非空 且降序
     * @return
     */
    public static Node mergeLinList(Node L1, Node L2) {

        //p始终指向L1未被扫描的首个节点
        Node p = L1;
        //q始终指向L2未被扫描的首个节点
        Node q = L2;
        //t始终指向新链表的尾部
        Node t = null;
        //使用L1或者L2的首个节点作为新链表的首个节点，不再申请内存空间
        if (p.data > q.data) {
            t = p;
            p = p.next;
        } else {
            t = q;
            q = q.next;
        }
        //r始终指向新链表的首个节点
        Node r = t;

        while (p != null && q != null) {
            //t的next域执行未归并的链表的两个首节点最大的一个
            //尾插法
            if (p.data > q.data) {
                t.next = p;
                p = p.next;
            } else {
                t.next = q;
                q = q.next;
            }
            t = t.next;
        }
        //若一个链表已经归并完毕,吧剩余节点直接并入新链表
        if (p == null) {
            t.next = q;
        }
        if (q == null) {
            t.next = p;
        }
        //新链表的头指针
        return r;

    }


}