今天课间的时候偶然看到了一个面试题：单链表的逆置，看了题解感觉乖乖的，貌似和以前看的版本不搭，于是重新进行了一番探究
单链表的逆置分为两种方法：头插法和就地逆置法，这两种方法虽然都能够达到逆置的效果，但还是有着不小的差别
头插法
算法思路：依次取原链表中的每一个节点，将其作为第一个节点插入到新链表中，指针用来指向当前节点，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<stdio.h> #include<malloc.h> typedef struct node { int data; struct node*next; }node; node*creat() { node*head,*p,*q; char ch; head=(node*)malloc(sizeof(node)); q=head; ch='*'; puts("单链表尾插法，？结束"); while(ch!='?') { int a; 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(" haved reversed："); print(a); return 0; }
程序截图
就地逆置法
//单链表定义 typedef struct ListNode{ int m_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; } return pRev; }
具体流程参见博客：http://www.cnblogs.com/dhls231/p/4773555.html
链表的翻转是程序员面试中出现频度最高的问题之一，常见的解决方法分为递归和迭代两种。最近在复习的时候，发现网上的资料都只告诉了怎么做，但是根本没有好好介绍两种方法的实现过程与原理。所以我觉得有必要好好的整理一篇博文，来帮忙大家一步步理解其中的实现细节。
我们知道迭代是从前往后依次处理，直到循环到链尾；而递归恰恰相反，首先一直迭代到链尾也就是递归基判断的准则，然后再逐层返回处理到开头。总结来说，链表翻转操作的顺序对于迭代来说是从链头往链尾，而对于递归是从链尾往链头。
具体实现可以参考这个博主：https://blog.csdn.net/FX677588/article/details/72357389
整体实现代码：
#include<iostream> using namespace std; struct node{ int val; struct node* next; node(int x) :val(x){} }; /***非递归方式***/ node* reverseList(node* H) { if (H == NULL || H->next == NULL) //链表为空或者仅1个数直接返回 return H; 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指向的下一个空间 } return newH; } /***递归方式***/ node* In_reverseList(node* H) { if (H == NULL || H->next == NULL) //链表为空直接返回，而H->next为空是递归基 return H; node* newHead = In_reverseList(H->next); //一直循环到链尾 H->next->next = H; //翻转链表的指向 H->next = NULL; //记得赋值NULL，防止链表错乱 return newHead; //新链表头永远指向的是原链表的链尾 } int main() { 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; }