引言
单链表因其独特的非连续存储方式，在内存管理上具有很高的灵活性。然而，这也意味着对它的操作比
数组等数据结构更加复杂。当我们需要将两个有序或具有某种特定关系的链表合并时，如果直接使用简
单的合并方法可能会导致效率低下。这时，交叉合并就显得尤为重要了。通过合理地调整节点连接顺
序，我们可以得到一个既保持原有链表特点又更高效的新链表。
基础语法介绍
在开始之前，让我们先来定义一下单链表的基本结构。一个典型的单链表节点通常包含两部分：存储数
据的域和指向下一个节点的指针。在Java中，我们可以这样定义：
接下来，我们将探讨如何利用这个简单的结构来实现两个链表的交叉合并。
基础实例
假设我们有两个已经排好序的单链表A和B，我们的目标是创建一个新的链表C，它由A和B交替组成。例
如，如果A=[1, 3, 5]，B=[2, 4, 6]，那么C应该是[1, 2, 3, 4, 5, 6]。
问题描述
给定两个链表的头结点 headA 和 headB ，编写一个函数来实现上述功能。
代码示例
class ListNode {
int val; // 存储的数据
ListNode next; // 指向下一个节点的引用
ListNode(int x) { // 构造函数
val = x;
next = null;
}
}
1
2
3
4
5
6
7
8
9
public ListNode mergeAlternately(ListNode headA, ListNode headB) {
ListNode dummy = new ListNode(0); // 创建一个虚拟头节点
ListNode current = dummy;
while (headA != null && headB != null) {
current.next = headA; // 先添加A的一个节点
headA = headA.next;
current = current.next;
current.next = headB; // 再添加B的一个节点
headB = headB.next;
current = current.next;
}
// 如果有一个链表先遍历完，则将另一个链表剩余部分直接链接到当前节点后面
if (headA != null) {
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
资源评论
