如何用Java编程语言实现两个已排序的单链表的合并操作?
时间: 2024-11-30 12:19:01 浏览: 11
在Java中,可以使用递归的方式来合并两个已排序的单链表。这里是一个简单的示例:
```java
public class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 如果其中一个链表为空,直接返回另一个
if (l1 == null) {
return l2;
} else 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;
}
}
```
这个`mergeTwoLists`函数首先检查两个列表是否有一个为空,如果为空则直接返回另一个非空链表。然后它会比较两个链表当前节点的值,将较小的节点设置为新链表的头节点,并对剩下的部分继续递归调用自身。
阅读全文