題目
將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回奕短。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的嚎货。
題解
合并兩個(gè)有序鏈表举农，類似于歸并排序中的一個(gè)子步驟瀑焦。主要是用兩個(gè)指針同時(shí)遍歷兩個(gè)鏈表腌且，將較小的一個(gè)鏈接到新鏈表上，同時(shí)后移指針榛瓮。當(dāng)兩個(gè)遍歷完至少一個(gè)鏈表時(shí)將另一個(gè)鏈表直接加到新鏈表的末尾铺董。
代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1,null);
ListNode p = dummy;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
p.next = (l1 != null)? l1 : l2;
return dummy.next;
}
}
知識(shí)點(diǎn)
鏈表解題通用小技巧，使用dummy節(jié)點(diǎn)禀晓，巧妙規(guī)避鏈表為空的情況精续。
