• 1 翻转思路
  • 1-1 整体的思路
  • 1-2 详细的思路
• 2 代码实现
• 3 运行结果

写个翻转链表算法，刚开始想到一个不错的思路。这个思路运行效率不低，时间复杂度为O(n)；可以不用分配额外的节点空间，空间复杂度为O(0)。现在把思路整理一下，并实现代码，测试运行结果。

1、 翻转思路

1-1 整体的思路

用一个while顺序遍历这个链表，然后把遍历到每个节点插入到链表头部。

1-2 详细的思路

蓝色箭头即赋值符号，比如在第2个结点的操作：

• step 2.1：front指针前移一位；
• step 2.2：把head节点的next值（即指向节点1的地址）赋给节点2；
• step 2.3：把节点2的地址赋给head节点的next；
• step 2.4：back指针前移一位；

while遍历条件可根据back不为空，即while(back)；

2、 代码实现

#include<stdio.h>       // NULL
#include<stdlib.h>      // malloc
#define ElemType int

typedef struct LNode{   // 定义单链表结点类型
    ElemType data;      // 数据域
    struct LNode *next; // 指针域
}LNode, *LinkList;      // LinkList相当于LNode*，即：struct LNode*

// 尾插法建立单链表L
LinkList listcreat_fromtail(LinkList L);
// 翻转链表L的算法
LinkList reverse_linklist(LinkList L);
// 把节点Node插入链表L头部
LinkList insert_head(LinkList L, LNode * Node);
// 输出链表L元素, flag=0为链表翻转前，flag=1为链表翻转后
void print_linklist(LinkList L, int flag);

int main(int argc, char *argv[])
{
    LinkList L;

    // 尾插法建立单链表L
    L = listcreat_fromtail(L);

    // 输出翻转前(flag=0)链表元素
    print_linklist(L, 0);

    // 翻转链表L
    L = reverse_linklist(L);

    // 输出翻转后(flag=1)链表元素
    print_linklist(L, 1);

    return 0;
}

// 翻转链表L的算法
LinkList reverse_linklist(LinkList L)
{
    LNode *back, *front;

    back = L->next; // step 0.1, init
    L->next = NULL; // step 0.2, init

    while(back){
        front = back->next;      // step x.1
        L = insert_head(L, back);// step x.2, step x.3
        back = front;            // step x.4
    }
    //back = front = NULL;         // for secure

    return L;
}

// 把节点Node插入链表L头部
LinkList insert_head(LinkList L, LNode * node)
{
    node->next = L->next; // step x.2
    L->next = node;       // step x.3

    return L;
}

// 输出链表L元素, flag=0为链表翻转前，flag=1为链表翻转后
void print_linklist(LinkList L, int flag)
{
    printf(flag ? "翻转后：\n" : "翻转前：\n");

    printf("单链表元素个数：%d, 分别是：", L->data);
    for(LNode* N = L->next; N; N = N->next){
        printf("%d ",N->data);
    }

    puts("\n");
}

//尾插法建立单链表L
LinkList listcreat_fromtail(LinkList L)
{
    int len, data;
    LNode *r;

    L = (LinkList)malloc(sizeof(LNode));
    L->data = 0; L->next = NULL; // L->data为链表长度
    r = L;                       // r为表尾指针

    printf("请输入插法建立单链表长度：");
    scanf("%d", &len);
    printf("请逐个输入链表元素：");
    while(len--){
        scanf("%d",&data);
        LNode *s=(LNode*)malloc(sizeof(LNode));
        s->data = data; s->next = NULL;
        r->next = s;
        r = r->next;
        L->data++;    // 链表长度+1
    }
    return L;
}

3、 运行结果

huashidazhongbeitushuguandeiMac-2:Wu_Being duzhe$ vim reverse_linklist.c
huashidazhongbeitushuguandeiMac-2:Wu_Being duzhe$ gcc reverse_linklist.c
huashidazhongbeitushuguandeiMac-2:Wu_Being duzhe$ ./a.out
请输入插法建立单链表长度：5
请逐个输入链表元素：1 2 3 4 5
翻转前：
单链表元素个数：5, 分别是：1 2 3 4 5 

翻转后：
单链表元素个数：5, 分别是：5 4 3 2 1 

huashidazhongbeitushuguandeiMac-2:Wu_Being duzhe$ ./a.out
请输入插法建立单链表长度：3
请逐个输入链表元素：1 2 3 4
翻转前：
单链表元素个数：3, 分别是：1 2 3 

翻转后：
单链表元素个数：3, 分别是：3 2 1 

huashidazhongbeitushuguandeiMac-2:Wu_Being duzhe$ 

Wu_Being博客声明：本人博客欢迎转载，请标明博客原文和原链接！谢谢！
《翻转链表算法和实现》：
http://blog.csdn.net/u014134180/article/details/78423589

如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。