算法描述 :
將兩個有序鏈表合并為一個新的有序鏈表并返回烘苹。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
算法實現(xiàn) :
Java實現(xiàn) :
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// l1為空時, 直接返回l2
if (l1 == null) {
return l2;
}
// l2為空時, 直接返回l1
if (l2 == null) {
return l1;
}
// 為l1構(gòu)造虛擬頭結(jié)點
ListNode dummyHead = new ListNode(-1);
dummyHead.next = l1;
ListNode p = dummyHead; // 比較用的指針
while (l2 != null) {
ListNode delNode = l2; // l2的頭結(jié)點,待移除
l2 = l2.next; // l2舍棄頭結(jié)點,后移一位
// 尋找delNode要添加的位置
while (p.next.val < delNode.val) {
p = p.next;
// p指向l1尾節(jié)點,直接將l2剩余部分追加l1上
if (p.next == null) {
p.next = delNode; // 此時delNode仍指向鏈表2的頭結(jié)點,而l2去指向鏈表2的第2個節(jié)點.故而返回delNode.
return dummyHead.next;
}
}
// l2中移除的節(jié)點添加到l1上
delNode.next = p.next;
p.next = delNode;
p = p.next; // 指針后移一位
}
return dummyHead.next;
}
}
