归并两个降序序链表为一个新的降序链表，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;    }}