《剑指offer》面试题25：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路一：归并排序的思想（非递归方式）
代码如下：
public ListNode merge1(ListNode list1,ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
} else {
ListNode node1 = list1;
ListNode node2 = list2;
// 确定合并后的新链表的头节点
ListNode mergeHead = null;
if (node1.val > node2.val) {
mergeHead = node2;
node2 = node2.next;
} else {
mergeHead = node1;
node1 = node1.next;
}
// 归并的过程
ListNode curNode = mergeHead;
while (node1 != null && node2 != null) {
if (node1.val > node2.val) {
curNode.next = node2;
node2 = node2.next;
} else {
curNode.next = node1;
node1 = node1.next;
}
curNode = curNode.next;
}
// 有一个链表归并完，另一个链表剩余的节点接上
if (node1 == null) {
curNode.next = node2;
}
if (node2 == null) {
curNode.next = node1;
}
return mergeHead;
}
}
思路二：每次比较两个节点的val的大小实际是重复的过程，可以借助递归函数实现。
代码如下：
public ListNode merge2(ListNode list1,ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
} else {
ListNode mergeHead = null;
if (list1.val > list2.val) {
mergeHead = list2;
mergeHead.next = merge2(list1,list2.next);
} else {
mergeHead = list1;
mergeHead.next = merge2(list1.next,list2);
}
return mergeHead;
}
}
