分别输入两个有序的整数序列(分别包含M和N个数据),建立两个有序的单链表,将这两个有序单链表合并成为一个有序单链表,并依次输出合并后的单链表数据。(可以用Java的LInkedlist类完成)
时间: 2024-10-10 09:05:02 浏览: 26
当你需要合并两个已排序的整数单链表时,可以使用双指针法,即创建一个新的链表,然后按照每个节点值的大小顺序逐一添加到新链表中。以下是使用Java的LinkedList类实现这个功能的一个简单步骤:
1. 创建一个`ListNode`类作为链表节点,包括一个整数值`val`和指向下一个节点的引用`next`。
```java
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
```
2. 定义一个函数`mergeSortedLists`来合并两个链表:
```java
public ListNode mergeSortedLists(ListNode headA, ListNode headB) {
// 如果链表A为空,直接返回链表B
if (headA == null) return headB;
// 如果链表B为空,直接返回链表A
if (headB == null) return headA;
// 初始化指针
ListNode dummy = new ListNode(0); // 创建虚拟头节点
ListNode tail = dummy; // 尾部指针
while (headA != null && headB != null) {
// 比较当前节点值,选择较小的添加到新链表
if (headA.val < headB.val) {
tail.next = headA;
headA = headA.next;
} else {
tail.next = headB;
headB = headB.next;
}
// 移动尾部指针
tail = tail.next;
}
// 添加剩余未遍历完的部分链表
if (headA != null) {
tail.next = headA;
} else {
tail.next = headB;
}
// 返回新链表的头部
return dummy.next;
}
```
3. 要输出合并后的链表,你可以遍历整个链表并打印每个节点的值:
```java
void printList(ListNode node) {
while (node != null) {
System.out.print(node.val + " -> ");
node = node.next;
}
System.out.println("null");
}
```