自己做网站可以挣钱吗,做网址导航网站,怎么做营销推广方案,如何优化网站排名Java 实现合并两个有序链表#xff1a;递归与迭代
在面试和算法题中#xff0c;合并两个有序链表是一个经典问题。通过这个问题#xff0c;不仅可以考察候选人的基础数据结构掌握情况#xff0c;还能测试他们对递归和迭代等编程技巧的应用能力。
本文将讨论如何使用 Java…Java 实现合并两个有序链表递归与迭代
在面试和算法题中合并两个有序链表是一个经典问题。通过这个问题不仅可以考察候选人的基础数据结构掌握情况还能测试他们对递归和迭代等编程技巧的应用能力。
本文将讨论如何使用 Java 递归与迭代两种方法来实现合并两个有序链表。
问题描述
给定两个有序链表 list1 和 list2将它们合并成一个新的有序链表并返回合并后的链表。
示例
输入list1 [1,2,4], list2 [1,3,4]输出[1,1,2,3,4,4]
方法一递归实现
递归是一种非常直观且简洁的方法特别适用于类似链表这种天然递归的数据结构。下面是基于递归的解决方案
public class MergeTwoSortedList {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 如果list1为空则直接返回list2if(list1 null) return list2;// 如果list2为空则直接返回list1if (list2 null) return list1;// 如果list1的值小于list2的值if (list1.val list2.val) {// 递归调用mergeTwoLists函数将list1的下一个节点和list2进行合并并将结果赋值给list1的nextlist1.next mergeTwoLists(list1.next, list2);// 返回list1return list1;} else {// 递归调用mergeTwoLists函数将list1和list2的下一个节点进行合并并将结果赋值给list2的nextlist2.next mergeTwoLists(list1, list2.next);// 返回list2return list2;}}
}递归方法的思路解析 基本情况 如果 list1 为 null则直接返回 list2因为此时 list2 仍然有值且不需要进一步操作。如果 list2 为 null则直接返回 list1同理。 递归情况 比较 list1 和 list2 的当前节点值。如果 list1 的值较小那么我们将 list1.next 与 list2 合并并将结果赋值给 list1.next然后返回 list1。否则将 list2.next 与 list1 合并并将结果赋值给 list2.next然后返回 list2。 递归结束 递归的结束条件是某一个链表到达末尾此时直接返回另一个链表剩余的部分。
方法二迭代实现
虽然递归方法简单易懂但在深度较大的链表上可能会导致栈溢出问题。因此使用迭代方法更为稳健。下面是使用迭代方法实现的代码
public class MergeTwoSortedList {public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {// 创建一个虚拟头节点以便于操作ListNode sentinel new ListNode(-1);ListNode prev sentinel;// 合并两个链表直到其中一个链表为空while (list1 ! null list2 ! null) {// 如果list1的当前节点值小于list2的当前节点值if (list1.val list2.val) {// 将list1的当前节点接到prev的后面prev.next list1;// 移动list1的指针到下一个节点list1 list1.next;} else {// 将list2的当前节点接到prev的后面prev.next list2;// 移动list2的指针到下一个节点list2 list2.next;}// 移动prev的指针到下一个节点prev prev.next;}// 如果list1还有剩余节点则将剩余节点接到prev的后面// 否则将list2的剩余节点接到prev的后面prev.next list1 null ? list2 : list1;// 返回合并后的链表的头节点return sentinel.next;}
}迭代方法的思路解析 创建哨兵节点 我们使用一个哨兵节点 sentinel 来简化链表头节点的处理最终返回 sentinel.next 即为合并后的链表头。 循环比较 使用 prev 指针遍历并合并两个链表将较小的节点接到 prev 后面并向前移动相应链表的指针。 处理剩余节点 当一个链表处理完后将另一个链表的剩余部分直接接在 prev 后面。 返回结果 最后返回 sentinel.next 即为合并后的链表。
测试代码
以下是一个简单的测试用例验证我们的实现是否正确
public static void main(String[] args) {ListNode listNode new MergeTwoSortedList().mergeTwoLists1(new ListNode(1, new ListNode(2)), new ListNode(2, new ListNode(4)));new MergeTwoSortedList().printListNode(listNode);
}运行结果为1 2 2 4表示合并操作成功。
结论
本文讨论了在 Java 中使用递归和迭代两种方式实现合并两个有序链表的方法。递归方法简洁直观但可能会遇到栈溢出问题而迭代方法稍微复杂一些但更为稳健。在实际应用中开发者可以根据具体情况选择合适的方法。
