单向链表的逆序，不使用额外节点存储实现

链表的逆序是常见考题，今天来简单学习使用如何实现单向链表的逆序。

逆序过程

初始链表状态

初始状态，prev是NULL，head指向当前的头节点A，next指向A节点的下一个节点B。首先从A节点开始逆序，将A节点的next指针指向prev，因为prev的当前值是NULL，所以A节点就从链表中脱离出来了，然后移动head和next指针，使它们分别指向B节点和B的下一个节点C（因为当前的next已经指向B节点了，因此修改A节点的next指针不会导致链表丢失）。逆向节点A之后，链表的状态如图（2）所示：

用这种方法依次向后逆序就可以了

逆序代码示例

结合上面图示理解

struct node *reverse(struct node *head)
{
    struct node *prev;//指向逆序完的链表的第一个节点
    struct node *next;//指向将要实现逆序的节点

    prev = NULL;

    while(head != NULL)
    {
        next = head->next;//把未逆序的head指向的节点的下一个节点让next保存,建立当前未逆序节点和下一个未逆序节点的链接
        head->next = prev;//让head指向的节点的下一个节点保存prev指向的节点，建立上一个逆序节点和当前未逆序节点的链接
        prev = head;//把head指向的节点让prev保存,逆序节点头指针前移
        head = next;//把next指向的节点让head保存，未逆序指针头结点后移
    }
    return prev;//逆序完成的头结点是prev，返回
};

完整代码检验

/*********************************************************************************
 *      Copyright:  (C) 2017 fanmaolin<[email protected]>
 *                  All rights reserved.
 *
 *       Filename:  make6.c
 *    Description:  This file 
 *                 
 *        Version:  1.0.0(08/05/2017)
 *         Author:  fanmaolin <[email protected]>
 *      ChangeLog:  1, Release initial version on "08/05/2017 01:00:52 PM"
 *                 
 ********************************************************************************/

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

#define LEN sizeof(struct node)
struct node
{
    int datanum;//数据号
    int data;//存储数据
    struct node *next;//指向下一个节点
};

int n;//统计是第几个节点

struct node *creat()
{
    struct node *head;//头指针，指向第一个节点
    struct node *p1 = NULL;//p1保存创建的新节点的地址
    struct node *p2 = NULL;//p2保存原链表最后一个节点的地址

    n = 0;
    p1 = (struct node *)malloc(LEN);//新建一个节点
    p2 = p1;
    if(p1==NULL)//创建节点失败
    {
        printf("creat fail\n");
        return 0;
    }
    else
    {
        head = NULL;//头指针为空
        printf("please input %d node\n",n+1);
        scanf("%d %d",&(p1->datanum), &(p1->data));//输入数据
    }
    while((p1->datanum)!=0)    //循环进行的条件
    {
        n = n + 1;//计算创建的节点数
        if(n==1)
        {
            head = p1;//head保存头结点的位置
            p2->next = NULL;//因为前面p1 = p2,而且现在只有一个节点，把next设置为空
        }

        else
        {
            p2->next = p1;//当不是第一个节点时，p2的next指向p1新创建的节点
        }

        p2 = p1;//p2保存p1的指向的节点，为p1创建新的节点做准备

        p1 = (struct node *)malloc(LEN);//p1创建新的节点
        printf("Please input %d node\n", n+1);
        scanf("%d %d", &(p1->datanum), &(p1->data));//向新的节点输入数据
    }

    p2->next = NULL;//最后一个节点指向为空


    free(p1);//释放结束时p1申请的内存空间
    p1 = NULL;//避免p1成为野指针
    return head;//返回头指针
};


void print(struct node *head)
{
    struct node *p;
    p = head;

    printf("head is %o\n", head);
    do
    {
        printf("p is %o ,datanum is %d, data is  %d, pnext is %o\n", p, p->datanum, p->data, p->next);
        //打印节点的地址，数据，下一个节点的地址
 make6.c                                                                                                                            
        p = p->next;//p指向下一个节点

    }while(p != NULL);
};

struct node *reverse(struct node *head)
{
    struct node *prev;//指向逆序完的链表的第一个节点
    struct node *next;//指向将要实现逆序的节点

    prev = NULL;

    while(head != NULL)
    {
        next = head->next;//把未逆序的head指向的节点的下一个节点让next保存,建立当前未逆序节点和下一个未逆序节点的链接
        head->next = prev;//让head指向的节点的下一个节点保存prev指向的节点，建立上一个逆序节点和当前未逆序节点的链接
        prev = head;//把head指向的节点让prev保存,逆序节点头指针前移
        head = next;//把next指向的节点让head保存，未逆序指针头结点后移
    }
    return prev;//逆序完成的头结点是prev，返回
};
int main()
{
    struct node *head;
    head = creat();
    print(head);
    head = reverse(head);//实现逆序
    print(head);//打印逆序结果
}

逆序结果：

[fanmaolin@Centeros lianbiao]$ gcc make6.c 
[fanmaolin@Centeros lianbiao]$ ./a.out 
please input 1 node
1
1
Please input 2 node
2
2
Please input 3 node
3
3
Please input 4 node
0
0
head is 35640020
p is 35640020 ,datanum is 1, data is  1, pnext is 35640060
p is 35640060 ,datanum is 2, data is  2, pnext is 35640120
p is 35640120 ,datanum is 3, data is  3, pnext is 0
head is 35640120
p is 35640120 ,datanum is 3, data is  3, pnext is 35640060
p is 35640060 ,datanum is 2, data is  2, pnext is 35640020
p is 35640020 ,datanum is 1, data is  1, pnext is 0

总结：

错误1

gcc编译，出现错误:expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ........

原因：多加了“}”，删除即可

分享

链表逆序重要的是思维理解，引入指针，操作指针实现。

参考链接：
http://blog.csdn.net/autumn20080101/article/details/7607148