本文共 1462 字，大约阅读时间需要 4 分钟。

面试题25：合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。例如下图所示。

1. 建立一个空的头节点，作为新的链表。
2. 比较两个链表的第一个节点的值，较较小者插入到新链表中。
3. 重复 2 的操作，直到一条链表为空。
4. 将另一条不空的链表插入到新链表之后。

代码实现：

package Question25;public class T01 {       public static void main(String[] args) {           Node node1 = new Node(1);        Node node2 = new Node(2);        Node node3 = new Node(3);        Node node4 = new Node(4);        node1.next = node4;        node2.next = node3;        Node result = solve(node1, node2);        while(result != null) {               System.out.println(result);            result = result.next;        }    }    public static Node solve(Node head1, Node head2) {           Node dummy = new Node(0);        Node t_dummy = dummy;        Node cur1 = head1, cur2 = head2;        while(cur1 != null && cur2 != null) {               if(cur1.value < cur2.value) {                   t_dummy.next = cur1;                t_dummy = t_dummy.next;                cur1 = cur1.next;            } else {                   t_dummy.next = cur2;                t_dummy = t_dummy.next;                cur2 = cur2.next;            }        }        if(cur1 != null) t_dummy.next = cur1;        if(cur2 != null) t_dummy.next = cur2;        return dummy.next;    }}class Node{       int value;    Node next;    public Node(int value) {           this.value = value;    }    @Override    public String toString() {           return "Node{" +                "value=" + value +                '}';    }}