剑指offer25 合并两个有序链表
文章目录
- 剑指offer25 合并两个有序链表
- 方法一:递归
- 方法二:迭代
- 参考文献
方法一:递归
思路:我们可以如下递归地定义两个链表里的merge操作(忽略边界情况,比如空链表等):
{ list 1 [ 0 ] + merge ( list 1 [ 1 : ] , list 2 ) list 1 [ 0 ] < list 2 [ 0 ] list 2 [ 0 ] + merge ( list 1 , list 2 [ 1 : ] ) otherwise \left\{\begin{array}{ll} \operatorname{list} 1[0]+\operatorname{merge}(\text { list } 1[1:], \text { list } 2) & \text { list } 1[0]<\operatorname{list} 2[0] \\ \text { list } 2[0]+\text { merge }(\text { list } 1, \text { list } 2[1:]) & \text { otherwise } \end{array}\right. {list1[0]+merge( list 1[1:], list 2) list 2[0]+ merge ( list 1, list 2[1:]) list 1[0]<list2[0] otherwise
也就是说,两个链表头部值较小的一个节点与剩下元素的merge操作结果合并。
算法
我们直接将以上递归过程建模,同时需要考虑边界情况。
如果l1或者l2一开始就是空链表,那么没有任何操作需要合并,我们只需要返回非空链表。否则,我们要判断l1和l2哪一个链表的头结点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;} else if (l2 == null) {return l1;} else if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}
递归方法代码可读性高,容易记忆和理解。
方法二:迭代
思路:我们可以用迭代的方法来实现上述算法。当l1和l2都不是空链表时,判断l1和l2哪一个链表的头结点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移动一位。
算法
1.我们设定一个哨兵节点prehead, 这可以在最后让我们比较容易地返回合并后的链表。
2.我们维护一个prev指针,我们需要做的是调整它的next指针。然后,我们重复以下过程,直到l1或者l2指向了null:
如果l1当前节点的值小于等于l2, 我们就把l1当前的节点接在prev节点的后面同时将l1指针往后移动一位。否则,我们对l2做同样的操作。不管我们将哪一个元素接在了后面,我们都需要把prev向后移动一位。
在循环终止的时候,l1和l2至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素斗殴比前面已经合并链表中的所有圆度都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表即可。
参考文献
[1] https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/