【手绘漫画】图解逆转单链表_单链表逆序（数据结构）

我是管小亮

发布于 2020-04-20 17:15:54

6420

发布于 2020-04-20 17:15:54

文章被收录于专栏：程序员管小亮的成长之路程序员管小亮的成长之路

1、?写在前面

这是一个很经典的题目，【单链表逆序】问题。

很多公司的面试题库中都有这道题，有的公司明确题目要求不能使用额外的节点存储空间，有的没有明确说明，但是如果面试者使用了额外的节点存储空间做中转，会得到一个比较低的分数。

那么如何在不使用额外存储节点的情况下，使一个单链表的所有节点逆序？

一千个人有一千个哈姆雷特，然后我都没看懂，，，最后是在手动推了一遍代码之后，才大概了解了这个过程，这里来手绘漫画图解一下！！！

这里使用的是迭代循环的思想，来分析这个问题。

2、?代码

typedef int ElementType;
typedef struct LNode *PtrToLNode;//单链表定义
struct LNode{
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToLNode List;

List Reverse(List L){
	//将单链表L逆转
	PtrToLNode new_head, old_head, temp;

	old_head=L;			//初始化当前旧表头为L
	new_head=NULL;		//初始化逆转后新表头为空

	while(old_head){	//当旧表头不为空时
		temp=old_head->Next;
		old_head->Next=new_head;
		new_head=old_head;
		old_head=temp;
	}
	L=new_head;			//更新L
	return L;
}

【分析】：这里解决这个问题的思路是：利用循环，从链表头开始逐个处理。循环设计中，最核心的要点是如何把握住 循环不变式。循环不变式 表示一种在循环过程进行时不变的性质，不依赖于前面所执行过程的重复次数的断言。

循环不变式主体是不变式，也就是一种描述规则的表达式。其过程分三个部分：初始，保持，终止。（1）初始：保证在初始的时候不变式为真。（2）保持：保证在每次循环开始和结束的时候不变式都为真。（3）终止：如果程序可以在某种条件下终止，那么在终止的时候，就可以得到自己想要的正确结果。————百度百科

对于本题来说，每轮循环开始前，都面临两个链表，其中 old_head 是一个待逆转的链表（即“旧”的链表头），而 new_head 是一个已经逆转好的链表（即“新”的链表头）。每轮循环执行好后，old_head 和 new_head 还是分别指向新的待逆转链表和已经逆转好的链表。

3、?正文

先给出程序的前面，确定单链表的定义方式。
在函数运行前，
1. 创建一个指针 new_head，指向内容为空（NULL）；
2. 创建一个指针 old_head，指向内容为链表头结点（L）；
3. 创建一个指针 temp；
4. 假设，Reverse( List L ); 函数接收的链表，内容为A,B,C,D（为了方便表示）；
上述过程如下图：

初始化后的状态如下：

temp = old_head->Next; 表示把 old_head->Next 指向 temp，就是 B 下面的 temp；

old_head->Next = new_head; 表示把 old_head->Next 指向 new_head，就把 old_head->Next 与 B 直接断开，指向 new_head；

完成了上一步，这一步就简单多了，即修改各个指针的指向位置，方便下一步继续将 B 连接到 A 的后面，如下图：

new_head=old_head;，然后 old_head=temp;，然后 temp=old_head->Next;（新一轮循环），移动新位置后如上；
重复循环上面的过程，直到 old_head 为 NULL；
最后执行 L=new_head;，更新 L，函数结束。

4、?实例

来自浙江大学数据结构的一道题，做了一些改编：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode{
    ElementType Data;
    PtrToLNode   Next;
};
typedef PtrToLNode List;

List Read(); 			/* 细节在此不表 */
void Print( List L ); 	/* 细节在此不表 */
List Reverse( List L );

int main(){
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

5 1 3 4 5 2

输出样例：

2 5 4 3 1

完整代码：

#include<stdio.h>
#include<stdlib.h>

typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode{
    ElementType Data;
    PtrToLNode  Next;
};
typedef PtrToLNode List;

List Read();
void Print(List L);
List Reverse(List L);

int main(){
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L2);

    return 0;
}

/*建立链表*/
List Read(){
	List current;
	List head=NULL;
	List prev=NULL;
	int len=0;
	scanf("%d",&len);
	while(len--){
		current=(List)malloc(sizeof(struct LNode));
		if(head==NULL)
			head=current;
		else
			prev->Next=current;

		current->Next=NULL;
		scanf("%d",¤t->Data);
		prev=current;
	}
	return head;
}

/*输出链表*/
void Print(List L){
	List p=L;
	if(p==NULL)
		printf("NULL\n");
	else
		printf("\n");
	while(p!=NULL){
		printf("%d ",p->Data);
		p=p->Next;
	}
}

/*单链表逆序*/
//代码来自，数据结构第二版（浙江大学），陈越等
List Reverse(List L){
	PtrToLNode new_head, old_head, temp;

	old_head=L;
	new_head=NULL;

	while(old_head){
		temp=old_head->Next;
		old_head->Next=new_head;
		new_head=old_head;
		old_head=temp;
	}
	L=new_head;
	return L;
}

示例跑通。