数据结构与算法之单链表的合并与逆置

这篇博客主要阐述单链表的合并与逆置，本人学习编程的时间也不是很久，如果在下面的文章中有讲解不周或有误的地方，欢迎各位大佬指正。

首先我们来熟悉一下单链表的结构：

1.单链表的结构

单链表是由一系列结点（由数据域和链域两部分构成）进行链式储存的一种线性表。它的一个组成单元叫做“结点”。它的特点是，在一个单链表中，有且仅有一个结点只有“后继”，并且有且只有一个结点只有“前驱”。示意图如下：

这里的图示一目了然，就不再进行赘述了。

2.链表的生成

要对链表进行操作，我们首先要生成链表，这里生成链表的代码如下：

Node* crateLinkedlist(){
	int i;
	int n;
	int x;
	Node* p;
	Node* q; 
	Node* head;
	
	printf("请输入要生成的链表长度:\n");
	scanf("%d",&n);
	printf("请输入数据：\n");
	
	head = NULL;
	for(i = 0;i < n;i++){
		scanf("%d",&x);
		p = (Node*)malloc(sizeof(Node));
		p->data = x;
		
		if(head == NULL){
			head = p;
			q = p;
		}
		else{
			q->next = p;
			q = p;
		}
		q->next = NULL;
	}
	
	return head;
}

具体的做法为：先由用户输入所需要链表的长度，计算机获取到这个值n。再生成一个空指针，下面进行n次循环，由用户进行输入每个结点的值。在循环中判断头指针是否为空，若空，则头指针指向新生成的结点;若非空，则将新生成的结点连接在最后一个结点的后面。这里用指针p来标记每次操作后链表的最后一个结点。

当然，这只是其中的一种做法，要由用户来主动输入链表的长度和每个结点的数据。除此之外，生成链表还可以用很多方法来完成。

3.链表的合并

两个链表合并的做法其实并不复杂，其实质就是让第一个链表的尾结点指向第二个链表的头结点即可。

代码如下：

   主函数代码：

	Node *p;
	Node *q;
	Node *another;
	p = crateLinkedlist(); 
	q = crateLinkedlist(); 
	another = combineList(&p,&q);
	printf("合并后的链表：");
	showlinkedlist(another);

先生成由指针p、q指向的两条链表，然后进行初始化，再调用合并的函数。

  合并函数代码：

Node* combineList(Node **head1,Node **head2){
	Node* head;
	head = *head1;
	
	while(head->next != NULL){
		head = head->next;
	}
	head->next = *head2;
	
	return *head1;
}

编译结果如下：

注意：这里的参数传递的是两个链表的指针的地址，而非指针！！理由如下：我们在C语言中都学习过，函数的形参与实参之间的关系为“单向值传递”，也就意味着，函数中形参仅仅与实参的值相同，它们实际上处于系统堆栈的不同位置（即地址不同）。那么，在这个函数中，如果参数为指针的话，用户一旦操作不慎，就极容易造成——内存泄漏。

4.链表的逆置

要对一个链表进行逆置，其中一个基本思路如下：

先生成一个空链表，然后对要进行逆置链表进行遍历，取出每个结点数据域的值，赋值给一个生成新的结点，并将这个新生成的结点采用“头插法”插入到新生成的空链表上，就可以完成链表的逆置。

代码如下：

Node* reverse(Node *head){
	Node* p;
	Node* q;
	Node* m;
	Node* l;
	
	m = (Node*)malloc(sizeof(Node));
	m->data = head->data;
	m->next = NULL;

	if(head->next != NULL){
		l = head->next;

		while(l){
		p =(Node*)malloc(sizeof(Node));
		p->data = l->data;
		p->next = NULL;
		p->next = m;
		m = p;
		l = l->next;
		}
	}
	
	return m;
}

编译结果如下：

为什么这里的参数又为链表的指针呢？

因为在这个函数中我们只需要遍历这个链表，并而不对链表中具体的值进行修改。所以仅传递指针即可。

当然头插法是链表逆置中的最简单有效的一种，还有许多别的方法大家可以思考。