JAVA递归合并两个有序的单链表,合并以后依然有序
时间: 2023-06-16 22:01:59 浏览: 58
可以使用递归的方式来合并两个有序的单链表,具体实现过程如下:
```java
public 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;
}
}
```
其中,`ListNode` 表示单链表的结点,包含一个整数值 `val` 和一个指向下一个结点的指针 `next`。在递归过程中,如果 `l1` 和 `l2` 中有任意一个为空,则直接返回另一个链表;否则,比较两个链表的头结点,将较小的那个结点作为新链表的头结点,然后递归处理剩下的结点,直到两个链表都为空,返回新链表的头结点即可。
相关问题
JAVA头节点无值,递归合并两个有序的单链表,合并以后依然有序
可以使用递归的方式来实现合并两个有序的单链表,具体思路如下:
1. 判断两个链表是否为空,如果其中一个为空,则返回另一个链表。
2. 比较两个链表的头节点的值,将值较小的节点作为新链表的头节点。
3. 递归合并两个链表的剩余部分,并将合并后的链表链接到新链表的后面。
下面是Java代码实现:
```java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head;
if (l1.val < l2.val) {
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
```
其中,ListNode 是单链表节点的定义,包含一个值和一个指向下一个节点的指针。这个方法的返回值是合并后的单链表的头节点。
用Java代码实现合并两个有序链表
可以使用以下代码实现合并两个有序链表:
```
public 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;
}
}
```
其中,ListNode 是一个链表节点的类,包含 val 和 next 两个属性。这个方法的思路是,比较两个链表的头节点的值,将较小的头节点作为合并后链表的头节点,然后递归地合并剩余的节点。