今天课间的时候偶然看到了一个面试题：单链表的逆置，看了题解感觉乖乖的，貌似和以前看的版本不搭，于是重新进行了一番探究

单链表的逆置分为两种方法：头插法和就地逆置法，这两种方法虽然都能够达到逆置的效果，但还是有着不小的差别

头插法

算法思路：依次取原链表中的每一个节点，将其作为第一个节点插入到新链表中，指针用来指向当前节点，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("nhaved 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;
}

下面我们来用图解的方法具体介绍整个代码的实现流程：

初始状态：

第一次循环：

第一次循环过后，步骤①：pTemp指向Head，步骤②：pCur指向P1，步骤③：pTemp->pNext指向NULL。

此时得到的pRev为：

第二次循环：

第二次循环过后，步骤①：pTemp指向P1，步骤②：pCur指向P2，步骤③：pTemp->pNext指向Head。

此时得到的pRev为：

第三次循环：

第三次循环过后：步骤①：pTemp指向P2，步骤②：pCur指向P3，步骤③：pTemp->pNext指向P1。

此时得到的pRev为：

第四次循环：

第四次循环过后：步骤①：pTemp指向P3，步骤②：pCur指向NULL，步骤③：pTemp->pNext指向P2。

此时得到的pRev为：

至此，单链表的逆置完成。

注就地逆置法转载出：灯火阑珊231

如果还没有看懂，可以去参考一下这个

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

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

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

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

　　最后一步：

2、非递归实现的程序

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;
}

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

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;                          //新链表头永远指向的是原链表的链尾
}

5、整体实现的程序：

#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;
}

　　
　感谢原作者，转载请注明出处：
http://blog.csdn.net/FX677588/article/details/72357389

头插法和就地逆置法是有区别的，其区别就在于逆置后的链表如果需要打印的话，那么头插法是从head开始的，而就地逆置则是从表尾开始的，从便捷性来说，头插法还是较之就地逆置法要好上那么一点点，当然因题而异了

最后

以上就是自信大炮为你收集整理的单链表的逆置（头插法和就地逆置）如果还没有看懂，可以去参考一下这个的全部内容，希望文章能够帮你解决单链表的逆置（头插法和就地逆置）如果还没有看懂，可以去参考一下这个所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。