将两个递增单链表合并为一个递减单链表
时间: 2024-09-21 10:07:16 浏览: 16
将两个递增排列的单链表合并成一个递减排列的单链表,可以采用以下步骤:
1. 创建一个新的头节点`newHead`,并初始化为第一个链表的头节点。
2. 定义三个指针,分别指向当前处理的第一个链表的头、第二个链表的头以及新链表的尾部。
3. 当两个链表都不为空时,进行以下操作:
a. 比较两个链表的当前节点值,取较小的那个作为新链表的新节点(因为我们要的是递减顺序)。
b. 将较小节点添加到新链表的尾部,并更新新链表的尾部指针。
c. 移动指向当前较小节点的链表的头指针,如果该链表还有剩余元素,则继续比较;否则切换到另一个链表。
4. 当其中一个链表遍历完后,将另一个链表剩余的部分直接连接到新链表的尾部。
5. 返回新链表的头节点`newHead`。
下面是示例代码:
```c
typedef struct Node {
int val;
struct Node* next;
} Node;
Node* mergeDecreasing(Node* head1, Node* head2) {
Node* newHead = (head1 && head1->val < head2->val) ? head1 : head2; // 新链表头
Node* tail = newHead;
while (head1 && head2) { // 只要任一链表非空
if (head1->val > head2->val) {
tail->next = head1;
tail = head1;
head1 = head1->next;
} else {
tail->next = head2;
tail = head2;
head2 = head2->next;
}
}
// 将剩余的一个链表连接到新链表尾部
if (head1) {
tail->next = head1;
} else {
tail->next = head2;
}
return newHead;
}
```