一沥匈、問題描述
給定兩個單鏈表蔗喂，都是遞增有序的，將它們合并高帖，使合并后的鏈表仍然有序弱恒。
二、解題思路
這種鏈表的問題我們最先想到是遞歸算法了棋恼，將兩個鏈表的第一個元素進(jìn)行比較 ，取較小的那個做為新鏈表的頭锈玉，剩下的分別作為兩個鏈表的頭結(jié)點(diǎn)爪飘，當(dāng)其中一個鏈表全都比較完了，則直接返回另一個鏈表拉背。
三师崎、代碼實現(xiàn)
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;
// 取下次合并的最小的節(jié)點(diǎn)，遞歸
mergeNode.next = mergeTwoListNode(firstHead.next, secondHead);
} else {
mergeNode = secondHead;
mergeNode.next = mergeTwoListNode(firstHead, secondHead.next);
}
return mergeNode;
}
