（链表）合并两个排序的链表

文章目录

- 前言：
- 问题描述：
- 解题思路：
- 代码实现：
- 总结：

前言：

此篇是针对链表的经典练习。

问题描述：

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围：
0≤n≤1000，−1000≤节点值≤1000
要求：
空间复杂度 O(1)，时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
在这里插入图片描述
或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

解题思路：

创建辅助头结点
在这里插入图片描述

在这里插入图片描述

代码实现：

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode* p1=pHead1;//指向无头结点的pHead1
    struct ListNode* p2=pHead2;//指向无头结点的pHead2
    struct ListNode* s;
    s=(struct ListNode*)malloc(sizeof(struct ListNode*));//创建辅助头结点（创建一个新的单链表存储排好序的结点）
    struct ListNode* z=s;//工作指针
    while (p1&&p2) {
        if (p1->val<=p2->val) {//比较
            z->next=p1;
            p1=p1->next;
        }else {
            z->next=p2;
            p2=p2->next;
        }
    z=z->next;
    }
    if (!p1) {
        z->next=p2;
    }else {
        z->next=p1;
    }
    return s->next;//返回第一个元素
}