前面,我们实现了链表的 环检测 操作,本篇来聊聊,如何合并两个有序链表。
有序链表合并
Leetcode 21. Merge Two Sorted Lists
示例
1 2
| Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
|
使用虚假的 Head 节点
定义一个临时虚假的 Head 节点,再创建一个指向 tail 的指针,以便于在尾部添加节点。
对 ListNode1 和 ListNode2 同时进行遍历,比较每次取出来的节点大小,并绑定到前面 tail 指针上去,直到最终所有的元素全部遍历完。
最后,返回 dummyNode.next
,即为新链表的 head 节点。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
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; } }
|
递归
使用递归的方式,代码比遍历看上去简洁很多,但是它所占用的栈空间会随着链表节点数量的增加而增加。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
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; } }
|
相关练习
参考资料