链表内容的补充1：单链表的归并以及逆置操作

65 阅读 0 评论 43 点赞

我是靠谱客的博主笨笨仙人掌，这篇文章主要介绍链表内容的补充1：单链表的归并以及逆置操作，现在分享给大家，希望可以做个参考。

在熟悉了单链表的构造以及操作函数后，需要补充一些链表的相关内容，包括两个重要的单链表操作单链表归并、单链表逆置以及静态链表，循环链表，双向链表三种结构。

1.单链表的归并

单链表归并主要目的便是将两条相互独立的单链表L1，L2归并至链表L1+2之中，基本思路同顺序表的归并类似：1）定义三个linklist类型的指针变量p1,p2,p3。p1,p2分别初始化指向L1,L2的头结点，p3初始化与p1相同，p3用于指示新链表L1+2的节点 2）使用while循环开始链表归并当p1的数据域小于p2的数据域时，将p1所指的结点归并入链表L1+2中，具体的方法为，使p1所指结点成为p3所指结点的后继，再将p3指向p1所指的结点，p1移动至原有p1的后继节点。同样地，当p2的数据域小于p1的数据域时，将p2所指的结点归并入链表L1+2中，具体方法类似 3）若p1或p2任何一指针为空时，退出while循环，此时进行条件的判断，如果p1为空，则将p3所指结点的后继结点指向p2指针所指的结点，如果p2为空，则将p3所指结点的后继结点指向p1指针所指的结点。 4）最后释放L2指针所指结点的空间，即释放L2链的头结点，将L1,L2两条链归并至L1+2链，该链表的头指针为L1。归并p1指针所指结点示意图以及实现代码如下：

void mergist(linklist l1,linklist l2,linklist l3)
{
    linklist p1,p2,p3;
    p1=l1->next;
    p2=l2->next;
    l3=p3=l1;
    while(p1!=NULL&&p2!=NULL)
    {
        if(p1->data<=p2->data)
        {
            p3->next=p1;
            p3=p1;
            p1=p1->next;
        }
        else
        {
            p3->next=p2;
            p3=p2;
            p2=p2->next;
        }
    }
    p3->next=p1?p1:p2;
    free(l2);
}

    head3=head1;
    mergist(head1,head2,head3);
    p=head3->next;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    return 0;

单链表归并p1指针所指结点示意图

2.单链表的逆置

单链表的逆置主要思路如下：1）建立一个头指针l，建立对应的头结点。使头结点的后继结点为空NULL 2）假设需要逆置的链表数据均存放于num[10]数组之中，逆置链表的指针记作p 3）利用for循环，在每一个循环之中，新建一个结点，使原有的指针p指向该结点。将该点记作结点p,先使结点p与头指针l指向的头结点l具有相同的后继域，头结点l的后继结点在第一次循环中记作NULL，在后n-1次循环中必须均设置为原有的结点p，这样才可以做到将每一次新建的结点均插入到原有结点的前驱位置，并且同时满足头结点的后继结点为每个循环新建的结点，从而方便输出。4）新建结点的数据域通过for循环从num[10]数组中获取。具体代码以及示意图如下：

void creatlist(linklist l,int num[10])
{
    l->next=NULL;
    linklist p;
    for(int i=0;i<10;i++)
    {
        p=(lNode*)malloc(sizeof(lNode));
        p->data=num[i];
        p->next=l->next;
        l->next=p;
    }
}

单链表逆置操作示意图