把两个单向链表融合，融合后也是有序的

方法思路是先比较链表一和链表二的第一个元素的值，将值较小的连接到主链表上，假定链表一的值小，那么链表一的指针后移，让链表一的第二个元素和链表二的第一个元素比较，以此类推。

public class MergeLinkedList {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.addByOrder(new Node(34));
        singleLinkedList1.addByOrder(new Node(67));
        singleLinkedList1.addByOrder(new Node(24));
        singleLinkedList1.addByOrder(new Node(79));

        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.addByOrder(new Node(64));
        singleLinkedList2.addByOrder(new Node(69));
        singleLinkedList2.addByOrder(new Node(57));
        singleLinkedList2.addByOrder(new Node(98));

        Node head1 = singleLinkedList1.getHead();
        Node head2 = singleLinkedList2.getHead();

        SingleLinkedList merge = SingleLinkedList.merge(head1, head2);
        merge.deleteHead();
        merge.list(merge.getHead());


    }
}

class Node {
    public int value;
    public Node next;//指向下一个节点

    //构造器
    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ‘}‘;
    }
}

class SingleLinkedList {
    private Node head = new Node(0);

    public void addByOrder(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.value >= node.value) {
                break;
            }
            temp = temp.next;
        }
            node.next = temp.next;
            temp.next = node;
    }

    public Node getHead() {
        return head;
    }

    public void list(Node node) {
        if (node.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = node.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    public static SingleLinkedList merge(Node n1, Node n2) {
        SingleLinkedList list3 = new SingleLinkedList();
        Node n3 = list3.head;
        while (n1 != null && n2 != null) {
            if (n1.value >= n2.value) {
                Node newNode = new Node(n2.value);
                n3.next = newNode;
                n2 = n2.next;
                n3 = n3.next;
            } else {
                n3.next = new Node(n1.value);
                n1 = n1.next;
                n3 = n3.next;
            }
        }

        while (n1 != null) {
            Node newNode = new Node(n1.value);
            n3.next = newNode;
            n1 = n1.next;
            n3 = n3.next;
        }

        while (n2 != null) {
            Node newNode = new Node(n2.value);
            n3.next = newNode;
            n2 = n2.next;
            n3 = n3.next;
        }
        return list3;
    }

    public void deleteHead() {
        this.head = getHead().next;
    }
}

注意代码：

while (n1 != null && n2 != null) {
            if (n1.value >= n2.value) {
                Node newNode = new Node(n2.value);
                n3.next = newNode;
                n2 = n2.next;
                n3 = n3.next;
            } else {
                n3.next = new Node(n1.value);
                n1 = n1.next;
                n3 = n3.next;
            }
        }

保证n3的next指向new Node后，栈空间中的newNode即便被重新赋值，堆空间中的new Node也被指针指向，由此就不会被JVM当成垃圾回收。

把两个单向链表融合，融合后也是有序的

原文：https://www.cnblogs.com/LostSecretGarden/p/14660208.html