Java两个有序链表的合并pta
时间: 2024-11-29 19:32:43 浏览: 35
在Java中,合并两个已排序的链表通常是通过递归或者迭代的方式实现的,目的是创建一个新的链表,其中包含原始两个链表的所有元素,并保持原有的升序顺序。这里我将简述一种常见的递归法:
**递归方法:**
假设你有两个链表`list1`和`list2`,它们分别代表两个已排序的列表。首先检查两个链表是否都为空,如果其中一个为空,直接返回另一个;若两者都不空,则比较当前节点值,将较小的那个节点作为结果的新头节点,然后递归地对剩余部分做同样的操作。
```java
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
```
相关问题
PTA2-2 两个有序链表序列的合并
PTA2-2 两个有序链表序列的合并是指将两个已经排好序的链表合并成一个新的有序链表。合并过程中需要按照节点的值大小依次连接节点,形成一个新的链表。
合并的方法是通过比较两个链表的节点值,将较小的节点优先连接到新链表中,然后移动指针到下一个节点,继续比较和连接,直到其中一个链表已经遍历完毕。最后,将另一个链表剩余的节点直接连接到新链表的末尾,合并完成。
以下是合并两个有序链表的步骤:
1. 创建一个新的头节点并初始化为空,用于存放合并后的链表。
2. 设置两个指针,分别指向两个链表的头节点。
3. 比较两个链表头节点的值,将较小的节点连接到新链表中,并将对应链表的指针向后移动一位。
4. 重复步骤3,直到其中一个链表已经遍历完毕。
5. 将剩余链表的节点直接连接到新链表的末尾。
6. 返回新链表的头节点。
阅读全文