合并两个有序链表为一个链表，最简单的java实现

现在有两个有序的链表，想把它们合成一个有序的链表。思路就是每次确定两个链表中的最小节点，然后调用递归依次往后推。

创建链表节点

 /**
 * @author David
 * @descritpion
 * @date 2019/9/29
 */
public class LinkedNode {

    private int val;

    private LinkedNode next;

    public LinkedNode(int val){
        this.val = val;
    }
    public LinkedNode(){
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public LinkedNode getNext() {
        return next;
    }

    public void setNext(LinkedNode next) {
        this.next = next;
    }

}

合并方法

public static LinkedNode mergeNode(LinkedNode node1, LinkedNode node2) {
        //如果两个链表都为null，直接返回null
        if (node1 == null && node2 == null) {
            return null;
        }
        //如果链表1为null，直接返回链表2
        if (node1 == null) {
            return node2;
        }
        //如果链表2为null，直接返回链表1
        if (node2 == null) {
            return node1;
        }
        //确定当前的最小节点，然后调用递归，依次求出之后的最小节点并连接，返回
        if (node1.getVal() <= node2.getVal()) {
            node1.setNext(mergeNode(node1.getNext(), node2));
           return node1;
        } else {
            node2.setNext(mergeNode(node2.getNext(), node1));
            return node2;
        }
    }

合并

public static void main(String[] args) {
        LinkedNode node1 = new LinkedNode(1);
        LinkedNode node2 = new LinkedNode(3);
        LinkedNode node3 = new LinkedNode(4);
        LinkedNode node8 = new LinkedNode(5);

        LinkedNode node4 = new LinkedNode(2);
        LinkedNode node5 = new LinkedNode(5);
        LinkedNode node6 = new LinkedNode(6);
        LinkedNode node7 = new LinkedNode(9);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node8);

        node4.setNext(node5);
        node5.setNext(node6);
        node6.setNext(node7);

        LinkedNode result = mergeNode(node1, node4);
        System.out.println(result);
    }

结果展示

欢迎各位大佬指点，批评。