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;}}
}

递归方法的思路解析：

1. 基本情况：

   • 如果 list1 为 null，则直接返回 list2，因为此时 list2 仍然有值，且不需要进一步操作。
   • 如果 list2 为 null，则直接返回 list1，同理。

2. 递归情况：

   • 比较 list1 和 list2 的当前节点值。如果 list1 的值较小，那么我们将 list1.next 与 list2 合并，并将结果赋值给 list1.next，然后返回 list1。
   • 否则，将 list2.next 与 list1 合并，并将结果赋值给 list2.next，然后返回 list2。

3. 递归结束：

   • 递归的结束条件是某一个链表到达末尾，此时直接返回另一个链表剩余的部分。

方法二：迭代实现

虽然递归方法简单易懂，但在深度较大的链表上可能会导致栈溢出问题。因此，使用迭代方法更为稳健。下面是使用迭代方法实现的代码：

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;}
}

迭代方法的思路解析：

1. 创建哨兵节点：

   • 我们使用一个哨兵节点 sentinel 来简化链表头节点的处理，最终返回 sentinel.next 即为合并后的链表头。

2. 循环比较：

   • 使用 prev 指针遍历并合并两个链表，将较小的节点接到 prev 后面，并向前移动相应链表的指针。

3. 处理剩余节点：

   • 当一个链表处理完后，将另一个链表的剩余部分直接接在 prev 后面。

4. 返回结果：

   • 最后返回 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 中使用递归和迭代两种方式实现合并两个有序链表的方法。递归方法简洁直观，但可能会遇到栈溢出问题；而迭代方法稍微复杂一些，但更为稳健。在实际应用中，开发者可以根据具体情况选择合适的方法。