数据结构—习题2.7 链表翻转（递归与迭代两种实现）LeetCode（206）

2024-02-01 18:55:28

链表的翻转是程序员面试中出现频度最高的问题之一，常见的解决方法分为递归和迭代两种。最近在复习的时候，发现网上的资料都只告诉了怎么做，但是根本没有好好介绍两种方法的实现过程与原理。所以我觉得有必要好好的整理一篇博文，来帮忙大家一步步理解其中的实现细节。
我们知道迭代是从前往后依次处理，直到循环到链尾；而递归恰恰相反，首先一直迭代到链尾也就是递归基判断的准则，然后再逐层返回处理到开头。总结来说，链表翻转操作的顺序对于迭代来说是从链头往链尾，而对于递归是从链尾往链头。下面我会用详细的图文来剖析其中实现的细节。

1.非递归（迭代）方式

迭代的方式是从链头开始处理，如下图给定一个存放5个数的链表。

首先对于链表设置两个指针：

然后依次将旧链表上每一项添加在新链表的后面，然后新链表的头指针NewH移向新的链表头，如下图所示。此处需要注意，不可以上来立即将上图中P->next直接指向NewH，这样存放2的地址就会被丢弃，后续链表保存的数据也随之无法访问。而是应该设置一个临时指针tmp，先暂时指向P->next指向的地址空间，保存原链表后续数据。然后再让P->next指向NewH，最后P=tmp就可以取回原链表的数据了，所有循环访问也可以继续展开下去。

指针继续向后移动，直到P指针指向NULL停止迭代。

最后一步：

非递归实现的程序

struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL || head->next == NULL) //链表为空或者仅1个数直接返回
        return head;
    
    struct ListNode* p,*newH;
    p=head;
    newH=NULL;
    
    while (p)                
    {
        struct ListNode* q;
        q= p->next;          
        p->next = newH;               
        newH = p;                    
        p = q;                   
    }
    
    return newH;
}

2.递归方式

我们再来看看递归实现链表翻转的实现，前面非递归方式是从前面数1开始往后依次处理，而递归方式则恰恰相反，它先循环找到最后面指向的数5，然后从5开始处理依次翻转整个链表。
首先指针H迭代到底如下图所示，并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数，所以整个过程NewH指针一直指向存放5的地址空间。

然后H指针逐层返回的时候依次做下图的处理，将H指向的地址赋值给H->next->next指针，并且一定要记得让H->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层H->next->next赋值的时候会覆盖后续的值。

继续返回操作：

上图第一次如果没有将存放4空间的next指针赋值指向NULL，第二次H->next->next=H，就会将存放5的地址空间覆盖为3，这样链表一切都大乱了。接着逐层返回下去，直到对存放1的地址空间处理。

返回到头：

递归实现程序

struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL || head->next == NULL)      
        return head;
    
    struct ListNode* newHead = reverseList(head->next); 
    head->next->next = head;                      
    head->next = NULL;                         
    
    return newHead;                          
}

3.带头结点链表的反转

题目描述：/* 设计一个算法，通过一趟遍历，将链表中所有的链接方向反转，仍利用原表的空间 */
思想：先将链表的头结点指针域置空，p指向链表的第一个结点；q指向*p的后继,然后将*p插入到头结点的后面。

void TurnList(LinkList &L) 
{
	struct LNode *p;
	p = L->next;
	L->next = NULL;
	while (p) 
	{
		LNode *q;
		q = p->next;     //   q指向*p的后继 
		p->next = L->next;
		L->next = p;    // 将*p插入到头结点之后 
		p = q;
	}
}

代码实现
main.cpp

#include<iostream>

using namespace std;

typedef struct LNode 
{
	int data;
	struct LNode *next;
}LNode, *LinkList;

int InitList(LinkList &L) 
{
	L = new LNode;
	L->next = NULL;
	return 1;
}

void TraveList(LinkList L)
{
	LNode *p;
	p = L->next;
	
	printf("遍历链表:\n");
	while (p) 
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//前插法创建单链表 
void CreateList(LinkList &L, int n) 
{
	L = new LNode;
	L->next = NULL;
	for (int i = n; i > 0; --i) 
	{
		printf("请输入第%d个元素的值:", i);
		struct LNode *p;
		p = new LNode;
		scanf("%d", &p->data);
		p->next = L->next;
		L->next = p;
	}
}

/*
思想：
先将链表的头结点指针域置空，p指向链表的第一个结点；
q指向*p的后继,然后将*p插入到头结点的后面。
*/
void TurnList(LinkList &L) 
{
	struct LNode *p;
	p = L->next;
	L->next = NULL;
	while (p) 
	{
		LNode *q;
		q = p->next;     //   q指向*p的后继 
		p->next = L->next;
		L->next = p;    // 将*p插入到头结点之后 
		p = q;
	}
}

int main() 
{
	LinkList L;

	if (InitList(L)) 
	{
		printf("链表初始化成功!\n");
	}
	else 
	{
		printf("链表初始化失败!\n");
	}

	printf("请输入链表的长度:\n");
	int n;
	scanf("%d", &n);
	CreateList(L, n);
	TraveList(L);

	printf("反转后的链表:\n");
	TurnList(L);
	TraveList(L);

	system("pause");

	return 0;
}

运行结果

码农公寓

相关文章