将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。
时间: 2024-11-06 12:24:35 浏览: 31
要将两个递增的有序链表合并成一个新的递增有序链表,你可以采用迭代或递归的方式进行。这里我会提供一个简单的迭代解决方案,因为迭代通常更直观且节省额外的空间。
首先,我们需要定义链表节点的结构:
```java
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
```
然后,我们可以创建一个辅助方法来进行链表的合并:
```java
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
// 创建一个新的头结点,初始值为空
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead; // 尾指针
// 比较两个链表当前元素,选择较小的一个添加到新链表
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
// 如果其中一个链表还有剩余元素,则将其添加到新链表末尾
if (l1 != null) {
tail.next = l1;
} else {
tail.next = l2;
}
// 返回新的头节点,即合并后的链表
return dummyHead.next;
}
```
这个方法的基本思想就是遍历两个链表,每次比较当前节点的值,将较小的节点添加到新链表的尾部,然后移动相应的指针。当其中一个链表遍历完时,将另一个链表剩余的部分直接添加到新链表的尾部。
阅读全文
相关推荐
![txt](https://img-home.csdnimg.cn/images/20241231045021.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![txt](https://img-home.csdnimg.cn/images/20241231045021.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![txt](https://img-home.csdnimg.cn/images/20241231045021.png)
![sln](https://img-home.csdnimg.cn/images/20250102104920.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)