关于java:面试题-合并两个有序链表

问题：合并两个有序链表

链表 L1: 1->2->4->9

链表 L2: 3->5>6->10->13

合并后：1->2->3->4->5->6->9->10->13

1. 筹备数据结构 及测试数据

Node 节点

public class Node {
    public Integer value;
    public Node next;
    // 结构
    public Node(){}
    public Node(Integer value) {this.value = value;}
    public Node(Integer value,Node next) {
        this.value = value;
        this.next = next;
    }

    // 打印链表
    public void print() {
       Node n = this;
       System.out.println("------------------------------------------------");
       while (n != null) {System.out.print(n.value);
           n = n.next;
           if (n != null) {System.out.print("-->");
           } else {System.out.println();
           }
       }
       System.out.println("------------------------------------------------");
    }
}

筹备测试数据

public class TestNode {public static void main(String[] args) {Node L1= getL1();
        Node L2= getL2();
        // 1-->2-->4-->9
        L1.print();
        // 3-->5-->6-->10-->13
        L2.print();}

    // 获取测试数据 L1
    public static Node getL1() {Node head = new Node(1,new Node(2,new Node(4,new Node(9))));
        return head;
    }
    // 获取测试数据 L2
    public static Node getL2() {Node head = new Node(3,new Node(5,new Node(6,new Node(10,new Node(13)))));
        return head;
    }
}

2. 解决方案 01

定义一个伪头节点 Head 而后遍历 L1 L2 比拟 Node 值 小的就追加到 Head 后边

private static Node mergeNodes(Node l1, Node l2) {if (l1 == null){return l2;}
        if (l2 == null) {return l1;}
        // 链表头
        Node head ;
        // 新链表增加的以后地位
        Node next ;
        // 先选出一个 2 个链表结尾的最小值
        head = next = l1.value > l2.value ? l2:l1;
        // 头指针向后挪动
        l1 = head == l1 ? l1.next : l1;
        l2 = head == l2 ? l2.next : l2;

        // 遍遍历 2 个链表
        while (l1 !=null && l2 != null) {
            // 遍历链表的最大值
            Node maxNode = null;
            // 链表 1 值大
            if(l1.value <= l2.value) {
                maxNode = l1;
                l1 = l1.next;
            } else {
                // 链表 2 值大
                maxNode = l2;
                l2 = l2.next;
            }
            // 增加到新链表 next 向后移
            next.next = maxNode;
            next = next.next;
        }

        // 判断哪个链表还没有遍历完 间接加到新链表开端
        next.next = l1 == null ? l2 :l1;
        // 返回 head
        return head;
    }

3. 解决方案 02

定义一个伪头节点 Head 而后遍历 L1 L2 比拟 Node 值 小的就追加到 Head 后边

应用递归 不必 while 循环

private static Node mergeNodesRec(Node l1, Node l2) {
        // 如果 l1 链表曾经遍历完了
        if (l1 == null) {return l2;}
        // 如果 l2 链表曾经遍历完了
        if (l2 == null) {return l1;}

        Node head ;

        if(l1.value <= l2.value) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        // 递归调用 设置 next
        head.next = mergeNodesRec(l1,l2);
        return head;
    }

本人写一写、用笔画一画 可能会恍然大悟 必定还有其余写法 欢送留言

有问题留言哦，或者公众号留言（回复快）：