一、问题描述
给定两个单链表，都是递增有序的，将它们合并，使合并后的链表仍然有序。
二、解题思路
这种链表的问题我们最先想到是递归算法了，将两个链表的第一个元素进行比较 ，取较小的那个做为新链表的头，剩下的分别作为两个链表的头结点，当其中一个链表全都比较完了，则直接返回另一个链表。
三、代码实现
public class ListNode {
int value;
ListNode next;
public ListNode(int value) {
this.value = value;
}
}
/**
* 合并两个有序单链表
* @param firstHead 第一个链表
* @param secondHead 第二个链表
* @return
*/
public ListNode mergeTwoListNode(ListNode firstHead, ListNode secondHead) {
// 递归出口
if (firstHead == null) {
return secondHead;
}
if (secondHead == null) {
return firstHead;
}
ListNode mergeNode; // 合并后的新链表
if (firstHead.value < secondHead.value) {
mergeNode = firstHead;
// 取下次合并的最小的节点，递归
mergeNode.next = mergeTwoListNode(firstHead.next, secondHead);
} else {
mergeNode = secondHead;
mergeNode.next = mergeTwoListNode(firstHead, secondHead.next);
}
return mergeNode;
}
