bicycle_journey-wallpaper
原文鏈接：https://wangwei.one/posts/java-algoDS-Merge-Two-Sorted-Linked-Lists.html
前面，我們實(shí)現(xiàn)了鏈表的 環(huán)檢測(cè) 操作，本篇來聊聊，如何合并兩個(gè)有序鏈表。
有序鏈表合并
示例
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
使用虛假的Head節(jié)點(diǎn)
定義一個(gè)臨時(shí)虛假的Head節(jié)點(diǎn)，再創(chuàng)建一個(gè)指向tail的指針，以便于在尾部添加節(jié)點(diǎn)。
對(duì)ListNode1和ListNode2同時(shí)進(jìn)行遍歷，比較每次取出來的節(jié)點(diǎn)大小，并綁定到前面tail指針上去，直到最終所有的元素全部遍歷完。
最后，返回 dummyNode.next ，即為新鏈表的head節(jié)點(diǎ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) {
ListNode dummyNode = new ListNode(0);
ListNode tail = dummyNode;
while(true){
if(l1 == null){
tail.next = l2;
break;
}
if(l2 == null){
tail.next = l1;
break;
}
ListNode next1 = l1;
ListNode next2 = l2;
if(next1.val <= next2.val){
tail.next = next1;
l1 = l1.next;
}else{
tail.next = next2;
l2 = l2.next;
}
tail = tail.next;
}
return dummyNode.next;
}
}
遞歸
使用遞歸的方式，代碼比遍歷看上去簡潔很多，但是它所占用的?？臻g會(huì)隨著鏈表節(jié)點(diǎn)數(shù)量的增加而增加。
代碼
/**
* 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) {
ListNode result = null;
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val <= l2.val){
result = l1;
result.next = mergeTwoLists(l1.next, l2);
}else{
result = l2;
result.next = mergeTwoLists(l1, l2.next);
}
return result;
}
}
