C语言实现两个有序链表的合并

C语言实现两个有序链表的合并

引用

CSDN

1.

https://blog.csdn.net/2401_83440536/article/details/139390988

本文将详细介绍如何使用C语言实现两个有序链表的合并。通过对比两种不同的实现方法，帮助读者理解链表操作的核心思路和优化技巧。

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

方法一：

思路

核心是通过比大小将小的节点取下来尾插。

解题方法

写一个新的链表，创造一个新头节点，因为是尾插所以需要找尾，但是每次找尾时间复杂度会变成n2，所以每次尾插后需要将尾更新。最后如果链表长度不一致再将非空链表取下来连接。

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode* head=NULL,*tail=NULL;
     //将头节点取小放入新节点
       if(list1->val<list2->val)
      {
         head=tail=list1;
         list1=list1->next;//链表迭代
      }
       else
      {
         head=tail=list2;
         list2=list2->next;//链表迭代
      }
    //取小的下来尾插
    while(list1 && list2)
    {
       if(list1->val>list2->val)
       {
        tail->next=list2;
        list2=list2->next;
       }
       else
       {
        tail->next=list1;
        list1=list1->next;
       }
       tail=tail->next;
    }
    if(list1)//list1不为空
    {
        tail->next=list1;
    }
    else//list2不为空
    {
        tail->next=list2;
    }
   return head;
}  

优化

思路

利用带哨兵卫的方法，开辟新链表的头节点，头节点不存数据。这样做就可以免去第一次比较再插入

解题方法

开辟一个节点空间赋值给新链表的头节点，不存数据，在链表完成后，将此节点删掉。

代码优化

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode* head=NULL,*tail=NULL;
    //带哨兵卫的办法
    head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    //取小的下来尾插
    while(list1 && list2)
    {
       if(list1->val>list2->val)
       {
        tail->next=list2;
        list2=list2->next;
       }
       else
       {
        tail->next=list1;
        list1=list1->next;
       }
       tail=tail->next;
    }
    if(list1)//list1不为空
    {
        tail->next=list1;
    }
    else//list2不为空
    {
        tail->next=list2;
    }
    struct ListNode* relHead=head->next;//因为要返回头节点所以需要将新链表的头存入
    free(head);
    return relHead;
}