《劍指offer》面試題25：輸入兩個單調(diào)遞增的鏈表盆佣，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則陨舱。
思路一：歸并排序的思想（非遞歸方式）
代碼如下：
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;
// 確定合并后的新鏈表的頭節(jié)點
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;
}
// 有一個鏈表歸并完翠拣，另一個鏈表剩余的節(jié)點接上
if (node1 == null) {
curNode.next = node2;
}
if (node2 == null) {
curNode.next = node1;
}
return mergeHead;
}
}
思路二：每次比較兩個節(jié)點的val的大小實際是重復的過程，可以借助遞歸函數(shù)實現(xiàn)游盲。
代碼如下：
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;
}
}
