問題描述
輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的節點仍然是遞增排序的，
示例1：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
限制：
0 <= 鏈表長度 <= 1000
解題思路
本題與普通陣列的歸并十分相似，根據題目描述，兩個鏈表l1，l2是遞增的，因此很容易想到使用雙指標l1和l2來遍歷兩個鏈表，根據雙指標所指向的l1.val和l2.val的大小關系確定添加結點的順序，當l1.val更小時，合并的鏈表中添加l1中的結點，當l2.val更小時，合并的鏈表中添加l2中的結點，當滿足l1和l2有一個鏈表遍歷完了之后，那么另外一個沒有遍歷完的鏈表就直接連接即可（注意，這里與陣列的歸并演算法不同，陣列中剩余一個鏈表需要一個一個的拷貝到新陣列中，而鏈表直接用next指標指向即可），
注意：這里有一個關鍵點是對于新的合并的鏈表，一定要定義一個不帶任何資料的頭結點
實作代碼
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head=new ListNode(-1); //定義頭結點
ListNode p=l1;
ListNode q=l2; //定義雙指標
ListNode r=head; //定義新的鏈表的指標
while(p!=null && q!=null){ //當其中一個鏈表遍歷完了，退出回圈
if(p.val<q.val){ //雙指標選擇最小的元素添加到新鏈表中
r.next=p;
p=p.next;
}else{
r.next=q;
q=q.next;
}
System.out.println(r.val);
r=r.next;
}
if(p!=null){ //當還有一個鏈表沒有遍歷完時，直接連接即可，
r.next=p;
}
if(q!=null){
r.next=q;
}
return head.next;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/259275.html
標籤：其他
下一篇：JAVA入門萬字總結