今天课间的时候偶然看到了一个面试题：单链表的逆置，看了题解感觉乖乖的，貌似和以前看的版本不搭，于是重新进行了一番探究
单链表的逆置分为两种方法：头插法和就地逆置法，这两种方法虽然都能够达到逆置的效果，但还是有着不小的差别
头插法
算法思路：依次取原链表中的每一个节点，将其作为第一个节点插入到新链表中，指针用来指向当前节点，p为空时结束。
核心代码
void reverse(node*head)
{
node*p;
p=head->next;
head->next=NULL;while(p)
{
q=p;
p=p->next;
q->next=head->next;
head->next=q;
}
}
以上面图为例子，说白了就是不断的将1后面的节点插入到head后面，即为头插法
完整代码
#include#includetypedefstructnode
{intdata;struct node*next;
}node;
node*creat()
{
node*head,*p,*q;charch;
head=(node*)malloc(sizeof(node));
q=head;
ch='*';
puts("单链表尾插法，？结束");while(ch!='?')
{inta;
scanf("%d",&a);
p=(node*)malloc(sizeof(node));
p->data=a;
q->next=p;
q=p;
ch=getchar();
}
q->next=NULL;return(head);
}void print(node*a)
{
puts("print");
a=a->next;while(a!=NULL)
{
printf("%d",a->data);
a=a->next;
}
}void reverse(node*head)
{
node*p,*q;
p=head->next;
head->next=NULL;while(p)
{
q=p;
p=p->next;
q->next=head->next;
head->next=q;
}
}
main()
{
node*a;
a=creat();
print(a);
reverse(a);
puts("\nhaved reversed：");
print(a);return 0;
}
View Code
程序截图
就地逆置法
//单链表定义
typedef structListNode{intm_nValue;
ListNode*pNext;
};
//单链表逆置实现
ListNode* ReverseList(ListNode*pHead)
{if (pHead == NULL || pHead->pNext ==NULL)
{
retrun pHead;
}
ListNode* pRev =NULL;
ListNode* pCur =pHead;while(pCur !=NULL)
{
ListNode* pTemp = pCur; //步骤①
pCur = pCur->pNext; //步骤②
pTemp->pNext = pRev; //步骤③
pRev =pTemp;
}returnpRev;
}
链表的翻转是程序员面试中出现频度最高的问题之一，常见的解决方法分为递归和迭代两种。最近在复习的时候，发现网上的资料都只告诉了怎么做，但是根本没有好好介绍两种方法的实现过程与原理。所以我觉得有必要好好的整理一篇博文，来帮忙大家一步步理解其中的实现细节。
我们知道迭代是从前往后依次处理，直到循环到链尾；而递归恰恰相反，首先一直迭代到链尾也就是递归基判断的准则，然后再逐层返回处理到开头。总结来说，链表翻转操作的顺序对于迭代来说是从链头往链尾，而对于递归是从链尾往链头。
具体实现可以参考这个博主：https://blog.csdn.net/FX677588/article/details/72357389
整体实现代码：
#include
using namespacestd;structnode{intval;struct node*next;
node(intx) :val(x){}
};/***非递归方式***/node* reverseList(node*H)
{if (H == NULL || H->next == NULL) //链表为空或者仅1个数直接返回
returnH;
node* p = H, *newH =NULL;while (p != NULL) //一直迭代到链尾
{
node* tmp = p->next; //暂存p下一个地址，防止变化指针指向后找不到后续的数
p->next = newH; //p->next指向前一个空间
newH = p; //新链表的头移动到p，扩长一步链表
p = tmp; //p指向原始链表p指向的下一个空间
}returnnewH;
}/***递归方式***/node* In_reverseList(node*H)
{if (H == NULL || H->next == NULL) //链表为空直接返回，而H->next为空是递归基
returnH;
node* newHead = In_reverseList(H->next); //一直循环到链尾
H->next->next = H; //翻转链表的指向
H->next = NULL; //记得赋值NULL，防止链表错乱
return newHead; //新链表头永远指向的是原链表的链尾
}intmain()
{
node* first = new node(1);
node* second = new node(2);
node* third = new node(3);
node* forth = new node(4);
node* fifth = new node(5);
first->next =second;
second->next =third;
third->next =forth;
forth->next =fifth;
fifth->next =NULL;//非递归实现
node* H1 =first;
H1= reverseList(H1); //翻转//递归实现
node* H2 = H1; //请在此设置断点查看H1变化，否则H2再翻转，H1已经发生变化
H2 = In_reverseList(H2); //再翻转
return 0;
}
