【头歌实训：拆分单链表】

头歌实训：拆分单链表

任务描述

本关任务：假设有一个带头结点的单链表L=（a₁b₁a₂b₂，…，a_n，b_n）。设计一个算法将其拆分成两个带头结点的单链表L1和L2：L1=（a₁，a₂，…，a_n），L2=（b_n，b_n−1，…，b₁）要求L1使用L的头结点。

相关知识

为了完成本关任务，你需要掌握：1.单链表的基本概念，2.如何创建、遍历单链表。

单链表的基本概念

单链表是线性表的链式存储结构实现。如下图所示：

单链表的头结点

为了操作方便，有时候会在单链表第一个元素结点的前面增加一个附加头结点，如下图所示：

单链表增加一个头结点的优点如下：

首结点的操作和表中其他结点的操作相一致，无需进行特殊处理；
无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。
单链表结点类型定义
单链表中结点类型LinkNode的定义如下:

typedef struct LNode //定义单链表结点类型
{
ElemType data; //存储元素
struct LNode *next; //指向后继结点
} LinkNode;

单链表的特点

单链表的特点：当访问过一个结点 p 后，只能接着访问它的后继结点，而无法访问它的前驱结点。

单链表插入一个结点

插入操作：将值为x的新结点s插入到p结点之后。
特点：只需修改相关结点的指针域，不需要移动结点。
插入操作如下图所示：

单链表删除一个结点

删除操作：删除p结点之后的一个结点。
特点：只需修改相关结点的指针域，不需要移动结点。
删除操作如下图所示：

删除操作的语句如下：

p->next = p->next->next;

创建单链表

头插法建立单链表

从一个空表开始，创建一个头结点。
依次读取线性表中的元素，生成新结点s。
将新结点插入到当前链表的表头上，直到结束为止。
头插法建立单链表如下图所示：

建表语句如下：

void CreateListF(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL;
for (int i = 0; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
s->next = L->next; //将结点s插在原开始结点之前,头结点之后
L->next = s;
}
}

尾插法建立单链表

从一个空表开始，创建一个头结点。
依次读取线性表中的元素，生成新结点s
将新结点插入到当前链表的表尾上，直到结束为止。
尾插法建立单链表如下图所示：

建表语句如下：

void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
L->next = NULL;
r = L; //r始终指向终端结点,开始时指向头结点
for (int i = 0; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点s
s->data = a[i];
r->next = s; //将结点s插入结点r之后
r = s;
}
r->next = NULL; //终端结点next域置为NULL
}

输出单链表

逐一扫描单链表L的每个数据结点，并显示各结点的data域值。

编程要求

根据提示，在右侧编辑器补充代码，完成函数void split(LinkNode *&L, LinkNode *&L1, LinkNode *&L2)，将单链表L拆分为L1和L2。

测试说明

平台会对你编写的代码进行测试：

输入格式

输入包括两行。
第一行为单链表中元素个数n。
第二行为空格隔开的n个整数。

输出格式

输出包括四行。
第一行为单链表的元素。每个数据后一个空格。
第二行显示提示信息。
第三行显示单链表L1中的元素。每个数据后一个空格。
第四行显示单链表L2中的元素。每个数据后一个空格。

样例输入

6
1 2 3 4 5 6

样例输出

L: 1 2 3 4 5 6
L->L1,L2
L1: 1 3 5
L2: 6 4 2

开始你的任务吧，祝你成功！

源代码：

#include "linklist.h"

//将单链表L拆分成两个单链表L1和L2。
void split(LinkNode *&L, LinkNode *&L1, LinkNode *&L2)
{
	//请在下面编写代码
	/**********************Begin**********************/
	LinkNode *p = L->next, *p1 = L1, *s2;  //获得指针p指向L的首元节点，指针p1指向L1   
                                            //且L，L1，L2均带有头节点      
	int i = 1;          //i用来计数判断该插入L1还是L2
	while(p)       //while循环遍历p
    {
        if(i % 2 != 0)  //尾插法
        {
            p1->next = p;   
            p1 = p;     //P1向下一结点移动
        }
        else        //头插法
        {
            s2 = (LinkNode *)malloc(sizeof(LinkNode));
            s2->data = p->data;         //这里不能写成s2 = p,
            s2->next = L2->next;        //因为这里要让s2->next = L2->next,写成s2 = p,就会改变p的next,这就是地址的神奇之处。。。。。。
            L2->next = s2;
        }
        p = p->next;        //P向下一结点移动
        i++;
    }
    p1->next = NULL;        //p1尾部置为NULL
	/***********************End***********************/
}

int main()
{
	LinkNode *L, *L1, *L2;
	int n;
	scanf("%d", &n);
	ElemType a[n];
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	InitList(L);					//初始化单链表L
	InitList(L1);					//初始化单链表L1
	InitList(L2);					//初始化单链表L2
    //LinkNode *L3 = (LinkNode *)malloc(sizeof(LinkNode));
    //L3->next = NULL;
    //if (L3) printf("==========empty===========\n");   //这里会输出
	CreateListR(L, a, n);			//创建单链表L
	printf("L: "); DispList(L);		//输出单链表L
	printf("L->L1,L2\n");
	split(L, L1, L2);				//单链表L拆分为L1和L2
	printf("L1: "); DispList(L1);	//输出单链表L1
	printf("L2: "); DispList(L2);	//输出单链表L2
	DestroyList(L1);				//销毁单链表L1
	DestroyList(L2);				//销毁单链表L2
	return 0;
}