面试题： 合并两个有序链表

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;    }}

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;    }

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;    }