devbox
编程探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

c语言实现单链表反转的四种方法_反转链表c语言

作者：编程探险家 | 2024-02-06 13:16:23

赞

踩

反转链表c语言

链表反转即假设有一链表1->2->3，反转后为3->2->1

以下的方法是没有头节点只有首元节点的情况

方法一：迭代法
如图所示，创建三个指针。小方块从左到右的值分别为1、2、3，假设
是以1->2->3的方向，那么，如果想实现链表反转，可以让中间的mid指针
从原来指向end变为指向pre，然后三个指针整体向右移动，mid再指向pre，直到end指向了NULL为止。最后让头指针指向mid即可，此时方向变为3->2->1
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

代码如下：

#include<Stdio.h>
#include<Stdlib.h>
typedef struct Node{
	int elem;
	struct Node *next;
}node;
node *initNode(){
	node *end=(node *)malloc(sizeof(node));//尾指针 
	node *p=(node *)malloc(sizeof(node));//首元节点 
	p->elem=1;
	p->next=NULL;
	end=p;
	for(int i=2;i<=3;i++){
		node *newnode=(node *)malloc(sizeof(node));
		newnode->elem=i;
		newnode->next=NULL;
		//尾插法 
		end->next=newnode;
		end=newnode;
	}
	return p;
}
void show(node *p){
	node *temp=p;
	while(temp){
		printf("%d",temp->elem);
		temp=temp->next;
	}
	printf("\n");
}
node *iteration(node *p){
	if(p==NULL||p->next==NULL){
		return p;
	}else{
		node *pre=NULL;
		node *mid=p;
		node *end=p->next;
		while(true){
			mid->next=pre;
			if(end==NULL){
				break;
			}
			//整体右移 
			pre=mid;
			mid=end;
			end=end->next;
		}
		p=mid;//原来的头指针指向mid（因为此时mid为首元节点）
		return p; 
	}
}
int main(void){
	node *p=initNode();
	show(p);
	p=iteration(p);
	show(p);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

方法二：递归法
该方法是通过递归，使得指针指向最后一个结点，然后从后往前改变指针的指向，从而实现反转。
有几点需要注意的：
1.需要建立一个头指针，返回该头指针。
2.需要建立一个从后往前递归的指针，从而不断地改变指针指向，即
head->next->next=head;
3.最重要的一点！！！
必须把原来结点的指针域置空，即head->next=NULL;不然，请看第二张图：
由于我们马上要写的函数当head指针指向1的时候，便结束循环，如果我们只写head->next->next=head;前面的2和3的指针域与确实分别指向1和2；
但是1的指针域指向的是2，当我们遍历的时候，由于循环结束的条件是：

while（temp）{
temp=temp->next;
}

当temp指针指向1的时候，temp->next指向2，即temp此时指向2，然后while循环判断不为空，从而执行temp=temp->next，又指向了1。1和2之间就形成了一个循环链表，永远不会结束循环，你会在屏幕上看到2121212121无限循环…，所以必须把原来的指针域置空！！！！
在这里插入图片描述
在这里插入图片描述

代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
	int elem;
	struct Node *next;
}node;
node *initNode(){
	node *end=NULL;
	node *p=(node *)malloc(sizeof(node));
	p->next=NULL;
	p->elem=1;
	end=p;
	for(int i=2;i<3;i++){
		node *newnode=(node *)malloc(sizeof(node));
		newnode->next=NULL;
		newnode->elem=i;
		end->next=newnode;
		end=newnode;
	}
	return p;
}
void show(node *p){
	node *temp=p;
	while(temp){
		printf("%d ",temp->elem);
		temp=temp->next;
	}
	printf("\n");
}
node *recursion(node *p){
	if(p==NULL||p->next==NULL){
		return p;
	}else{
		node *newnode = recursion(p->next);
		p->next->next=p;
		p->next=NULL;
		return newnode;
	}
}
int main(void){
	node *p=initNode();
	show(p);
	p=recursion(p);
	show(p);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

有一点需要提一下：
node *newnode = recursion(p->next);
…

return newnode;
返回值是newnode，这个值不变，一直指向末尾（即反转后链表的头指针）
而每次返回p都会左移，直到移动到原链表第一个结点为止。

方法三：新建链表
该方法是新建一个链表，然后循环要反转的链表中的每个元素，通过头插法（因为头插法会改变数据原来的顺序，正好适合反转）插入到新链表中的方法。
在这里提一下：
有头结点和没有头结点的头插法写法是不一样的，而尾插法写法是一样的
有头结点的头插法：

node *head;//头结点
head->next=NULL;
node *newnode=(node *)malloc(sizeof(node));
newnode->next=head->next;
head->next=newnode;

  • 1
  • 2
  • 3
  • 4
  • 5

没有头结点的头插法：

node *p;//首元节点
p->elem=xxx;
p->next=NULL;
node *newnode=(node *)malloc(sizeof(node));
newnode->next=p;
p=newnode;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

无论是否有头结点的尾插法：

node *end=NULL;//尾指针
node *head=(node *)malloc(sizeof(node));//有头结点
//只有首元结点则node *p=(node *)malloc(sizeof(node));和上面一样
head->next=NULL;
end=head;
node *newnode=(node *)malloc(sizeof(node))
end->next=newnode;
end=newnode;


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
	int elem;
	struct Node *next;
}node;
node *initNode(){
	node *end=NULL;
	node *p=(node *)malloc(sizeof(node));
	p->next=NULL;
	p->elem=1;
	end=p;
	for(int i=2;i<4;i++){
		node *newnode=(node *)malloc(sizeof(node));
		newnode->next=NULL;
		newnode->elem=i;
		end->next=newnode;
		end=newnode;
	}
	return p;
}
void show(node *p){
	node *temp=p;
	while(temp){
		printf("%d ",temp->elem);
		temp=temp->next;
	}
	printf("\n");
}
node *head(node *p){
	node *new_p=NULL;
	node *temp=NULL;
	if(p==NULL||p->next==NULL){
		return p;
	}
	while(p){
		temp=p;
		p=p->next;
		temp->next=new_p;
		new_p=temp;
	}
	return new_p;
}
int main(void){
	node *p=initNode();
	show(p);
	p=head(p);
	show(p);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

注意一点：

while(p){
		temp=p;
		p=p->next;
		temp->next=new_p;
		new_p=temp;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

这部分代码中，p=p->next必须在temp=p后面，如果放在最后面，由于
temp->next=new_p，使得temp指向的结点到后面所有结点的链断了（因为该节点的指针域不指向后面而指向new_p了），但是此时p也指向该结点，所以，此时的p=p->next为NULL（因为断链了）

方法4：在原链表上直接反转
思路是这样的：我们需要创建两个指针，如下图（图中有一个头指针p没画出来）。然后把第二个结点移除，操作类似于删除结点，就是让第一个结点的指针域指向第三个结点，
即pre->next=end->next，然后让第二个结点指向第一个结点，
即end->next=p，然后p指向end，接下来让end指针指向pre->next，即第三个结点。一直循环下去，直到end为NULL。

在这里插入图片描述

代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
	int elem;
	struct Node *next;
}node;
node *initNode(){
	node *end=NULL;
	node *p=(node *)malloc(sizeof(node));
	p->next=NULL;
	p->elem=1;
	end=p;
	for(int i=2;i<4;i++){
		node *newnode=(node *)malloc(sizeof(node));
		newnode->next=NULL;
		newnode->elem=i;
		end->next=newnode;
		end=newnode;
	}
	return p;
}
void show(node *p){
	node *temp=p;
	while(temp){
		printf("%d ",temp->elem);
		temp=temp->next;
	}
	printf("\n");
}

			pre=mid;
			mid=end;
			end=end->next;
		}
		p=mid;
		return p;
	}
}
node *recursion(node *p){
	if(p==NULL||p->next==NULL){
		return p;
	}else{
		node *newnode = recursion(p->next);
		p->next->next=p;
		p->next=NULL;
		return newnode;
	}
}
node *head(node *p){
	node *new_p=NULL;
	node *temp=NULL;
	if(p==NULL||p->next==NULL){
		return p;
	}
	while(p){
		temp=p;
		p=p->next;
		temp->next=new_p;
		new_p=temp;
	}
	return new_p;
}
node *local(node *p){
	node *pre=NULL;
	node *end=NULL;
	if(p==NULL||p->next==NULL){
		return p;
	}
	pre=p;
	end=p->next;
	while(end){
		pre->next=end->next;
		end->next=p;
		p=end;
		end=pre->next;
	}
	return p;
}
int main(void){
	node *p=initNode();
	show(p);
	p=recursion(p);
	show(p);
	p=head(p);
	show(p);
	p=local(p);
	show(p);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/编程探险家/article/detail/62883
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号