单链表分离(头插法和尾插法的结合,理解指针变换)_3.对任务1或者2中创建的某一个单链表{a1,b1,a2,b2,...,an,bn},编写一个算法将

问题:

●有一个带头节点的单链表 L={ a1,b1 , a2, b2......,an,bn }

●设计一个算法将其拆分成两个带头结点的单链表 L1 和 L2;

●L1 = {a1, a2 , a3 , a4....,an} , L2 = {bn,bn-1,...,b1}

●要求L1使用L的头结点

分析:

我们分开链表的实质就是,让 a 和 b 分开, 然后 a用尾插法, b 用头插法
至于头插法和尾插法, 我的上一个文章已经详细讲解了,

现在开始我们的操作:

首先,读题,第四点,题上要求,L1直接使用L 的头结点,那我们就不用为L1头结点分配空间了,
并且 L 的节点也不用分配空间了
那我们就可以,直接利用 L这个链表,在这个链表上构建 L1 , 然后 L2的话,把b提出来,
这时候 a 的结点会因为 b 的断开而 断开,此时,我们需要链接 ,a 的各个结点 ,我们
先从L1的头结点开始链接

我们首先就去创建链表的头结点

L1 = L;

L2=(LinkList*)malloc(sizeof(LinkList));

L2->next =NULL

---

这是刚开始的时候,我们把 L1 和 L2 的头结点定义了, L2 另外起家,L1 使用L

接下来,就是进行L1 和 L2 的构建了

a1 在前,所以我们就先构建 L1 , L1 肯定包括头结点吧
所以, 链接 a1 和 头结点,就是让 L1头结点的尾指针指向 a1 

所以这个时候,我们需要定义一个指针,来充当L1的新节点,然后把新节点送到L1尾节点的尾指针就行了

LinkList *r1 = L1;  //来定位L1的尾结点的位置,初始的时候只有头结点L1,所以r1指向L1

LinkList *p ;    //定义 p指针来充当L1 的新节点, 
p=L->next;    //刚开始新节点就是a1 ,也就是L头结点的后继节点

---

这里是把节点a1 传递给了 p ,包括a1的尾指针和数据,为了方便我们后续的操作

现在,我们的 a1 充当新节点,我们已经传给了 P, 

先进行尾插法

直接把 p 送到L1尾结点 r1  的尾指针 r1->next ,

r1->next=p;

 接下来我们 L1 的第一个节点就新建完成了,然后我们需要 对 b1 进行定位,然后用头插法把 b1送到

L2 , 

我们需要定位 b1 ,所以 p 作为对新节点操作的指针, p要指向 b1, 所以 p 向后移动

p = p->next;

此时我们已经拿到了,b1 这个节点, 现在是 p 来进行管理,用到头插法 把 p 插入到L 2头结点的后继节点

我们需要做的就是, 让L2 的后继指针指向 b1 ,然后b1 指向 b1 插入前的 L2->next ,从而形成闭环

根据头插法,我们要让

p->next = L2->next;    //先把L2头结点的尾指针赋值给 新节点b的尾指针,

L2->next = p;                //然后把 新节点  b 1 插入到 L2头结点的后面,就是把 p 的指针 传入到头结点的尾指针

---

强调,这两步不能颠倒,我们建立链表肯定会进行这两步操作是无疑的, 但是当我们覆盖一个指针的时候,要考虑这个指针里面是否存着我们需要的信息,  插入前,L2->next 里面存放的是第一个结点 的位置, 我们还要用到, 所以要先进行这一步, 然后再把新节点的位置给 头结点的尾指针. 

注意: 覆盖指针的时候,考虑我们要实现什么操作, 覆盖的指针存放的有没有我们需要的信息, 并且要修改哪些指针,这个要搞清楚

 此时 , 我们已经 新建了L1 链表 ,插入了新元素 a1 

                     新建了L2 链表, 插入了元素  b1

但是, 我们接下来要对下一个新节点 a2  ,进行操作, 那 a2 的位置信息我们怎么寻找呢, 要知道, 我们把 b1 分离的时候, 已经

把 b1->next 变成了 L2->next . 所以 a2 的信息自然就丢失了

那怎么办呢?

最好的办法就是 , 在修改 b1->next 之前, 把 a2 的位置信息 (b1->next )存储起来,  我们用q来存储

LinkList *q;

q = p->next;        // a 1 和 b1 和  a2  分别对应  r1    p   q 

---

通过b->next 来指引存储 q 的位置

所以我们在进行 对 a1  , b1  , a2  进行一个循环的操作  , 

我们现在理清一下思路, 

第一步: 我们创建了 L1 和 L2 的头结点 , 

L1=L;

L2 = (LinkList *)malloc(sizeof(LinkList));

L2->next = NULL;

第二步: 对 L 从头结点开始, 为了对节点进行遍历分割

第三步: 先定义 r1 是L1的尾节点 ,  p是新插入的节点 ,然后因为 b结点分隔后, a 2失去联系 , 要用 q 来存储 b 的尾指针 

LinkList *p , *q , *r1;

r1=L1;                //刚开始, L1 是空节点, 所以指向 头结点 

第四步: 我们通过尾插法, 先构建 L1 ,让 p 指向 L1的尾指针 r1 , 

p=L->next;                //初始的时候, a1是L的新节点

r1 ->next = p;          // 然后把新节点的指针赋值给L1 尾结点 r1 的尾指针

r1 = p;                // 此时L1的尾节点变成 p , 所以 r1 指向 p

第五步: 接着处理下一个节点 b1 (当然指向新节点的指针 p 需要往后移动), 把 b1 揪出来 . 此时, 为了避免对 b1 的指针进行覆盖后, 会失去 a2 的联系 ,然后用 q 来存储

p = p->next;

LinkList *q;   //这是这一步才得出的操作, 上面的说过了,再陈述一遍

q = p->next;  //存储 a2位置, 此时 p 是 b1 , 其后继指针当然是 a2

第六步: 可以对 b1进行操作,头插法, 变换 b1 的指针指向L2 的头结点的尾指针 ,  L2 的尾指针再指向 b1

p->next = L2->next;

L2 ->next = p;

第七步:  接下来, 我们接着让 指向 新节点指针 p 向后移动 , 那怎么移动到 a2 呢 ? 我们刚才存储了 a2到 q ,所以直接赋值一下就可以

p = q 

         因为我们存储了 a2 ,所以我们就可以把 a2 链接到 a1 后边.

         此时, L1的尾结点是r1(a1),新节点就是 p (a2),我们就可以链接了

r1 ->next = p;

第八步:链接之后,L1 的尾结点,又更新了, r1 指向新节点 p , 就是 a2 ,那就需要 变换r1 指向 a2 ,然后 p指向下一个新节点, b2 ,如此循环往复

r1 = p; 

p = p->next;

第九步:我们会发现 , p 又指向了 b2 , r1指向了L2的新节点 a2 ,  我们还是需要对 b2 进行头插法 , 第八步我们已经 进行了对 L1的更新

,就是对新节点 a2 进行的尾插法操作 , 接下来 就又是 对 b 进行头插法, 如此循环 , 

那我们是不是就可以用 一个 w

,,,,,

那怎么看最后一步呢,由题可知, a1 ,b1,,,,,an ,bn

所以,我们就把第一种情况当作是最后一步来讨论

 所以,当什么时候,结束呢?

当判断bn 后面没有结点的时候, 我们就可以结束了, 刚才我们用 q 来存放 b 断开联系后的下一个结点 ,那当bn的尾指针是NULL的时候 , 我们就可以结束了, 意思就是不用连接了, 因为 bn 断开后, 没有后继节点了.

所以,判断q 是空就可以 跳出操作了,

跳出操作后, 我们还要注意,虽然我们不用链接了, 但是 r1 是L1 的尾结点, 尾结点没有置空,它的尾指针还存着 bn的位置指针,

说白了 , 就是他还需要链接  bn 后继空指针, 尾结点的尾指针反正是空, 所以跳出的时候 , 我们再进行置空就可以了.

那现在思路我们已经理清了 , 那什么时候开始循环呢 ? 哪些 步骤我们可以开始循环  ,

在创建L1 和 L2 头结点 后 ,  我们就开始往 L1 和 L2 链接新节点了

此时是 把  新节点 p 送到 r1->next , 链接 a 的新节点 ,并且 r1 指向 L1的尾结点 p

r1->next = p;

r1 = p;

然后 接着让 指向新节点的 p 指针往后移动 ,  需要把 b1 链接 到 L2  , 需要把 b1 ->next覆盖, 所以我们用 q 来存储会丢失的指针 

p = p->next;

q = p->next;

接着 , p->next = L2->next;

           L2->next = p;

接下来又需要链接 新节点 a 了 ,我们还需要让 p 来指向 新节点 a , 但 新节点  a  的位置刚才我们覆盖了, 存储在了 q 中, 所以需要赋值给 p

p= q;

现在 , 我们又一次需要对 a , 进行操作了 ,然后进行的操作还是 r1->next = p; 链接 b , 存储下一个结点 a , 

我们此时又回来了 , 所以我们就知道了 ,循环哪一部分了 , 

while( )
{
    r1->next = p;
    r1=p;
    p = p->next;
    q = p->next;
    p->next = L2->next;
    L2->next = p;
    p = q;
}

其实我们循环的是这一部分, 那循环判出的条件是 , q为空的时候 , q存放的是链接接 an 和 an+1 

的数据 , 当 an+1 是空的时候 , 那我们就可以跳出了 , 那直接用 

q!=NULL

可以吗 ? 我认为不妥 , 因为, 进入循环之前  q 我们还没有赋值 ,那就是 NULL , 

所以, 这又引出了 ,怎样才能进入循环, 

当仍然有新节点可以插入的时候, 我们就可以进入循环, 

所以 用  p!=NULL , 就很妙 !(p指向的就是待操作的新结点)

因为, 我们在循环结束的最后一步, 又把 b 断开后的指针存放起来了 ,并传递给了

p , 用来指向新节点, 那当操作 bn 时候 , p->next 就是空, 此时 q里存放的是空

传递给p 的也是空 ,

综上所述 , 我们判出的条件是 , p!=NULL 即可

L2的尾指针不用处理 , 因为是头插法, ,而L1 的尾结点是 r1 , 然后循环结束 ,也没有修改,链接 新指针 p(NULL)

所以 , 我们需要亲自链接   r1 ->next =NULL;

源代码如下:

void split(LinkList *&L,LinkList *&L1,LinkList*&L2)
{	
	LinkList *p = L->next, *q, *r1;
	L1 = L;
	r1 = L1;
	L2 =(LinkList*)malloc(sizeof(LinkList));
	L2->next = NULL;
	while(p!=NULL)
	{
		r1->next = p;
		r1=p;
		p = p->next;
		q = p->next;
		p->next = L2->next;
		L2->next = p;
		p = q;
	}
	r1->next = NULL;
}

测试代码如下:

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;
    struct LNode *next;     //指向后继结点
} LinkList;
 
void DispList(LinkList *L);  //输出单链表
void CreateListR(LinkList *&L,ElemType a[],int n); //尾插法建立单链表
void split(LinkList *&L,LinkList *&L1,LinkList*&L2);//分离链表
int main()
{
    LinkList *L1, *L2,*L;
    ElemType a[10]= {1,2,3,4,5,6,7,8,9,10};
    CreateListR(L, a, 10);
	printf("输出L表结果:");
	DispList(L);
	split(L,L1,L2);
    printf("L1表结果：");
    DispList(L1);
    printf("L2结果：");
    DispList(L2);
    return 0;
}
 
 
void CreateListR(LinkList *&L,ElemType a[],int n)//尾插法建立单链表
{
    LinkList *s,*r;
    int i;
    L=(LinkList *)malloc(sizeof(LinkList));     //创建头结点
    L->next=NULL;
    r=L;                    //r始终指向终端结点,开始时指向头结点
    for (i=0; i<n; i++)
    {
        s=(LinkList *)malloc(sizeof(LinkList));//创建新结点
        s->data=a[i];
        r->next=s;          //将*s插入*r之后
        r=s;
    }
    r->next=NULL;           //终端结点next域置为NULL
}
  
void DispList(LinkList *L)  //输出单链表
{
    LinkList *p=L->next;
    while (p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
void split(LinkList *&L,LinkList *&L1,LinkList*&L2)
{	
	LinkList *p = L->next, *q, *r1;
	L1 = L;
	r1 = L1;
	L2 =(LinkList*)malloc(sizeof(LinkList));
	L2->next = NULL;
	while(p!=NULL)
	{
		r1->next = p;
		r1=p;
		p = p->next;
		q = p->next;
		p->next = L2->next;
		L2->next = p;
		p = q;
	}
	r1->next = NULL;
}