结构之美：单链表逆序

转自：结构之美：单链表逆序


题目：已知单向链表的头结点head，写一个函数把这个链表逆序 (Intel)
这个题目算是考察数据结构的最基础的题目了，下面我们一步步解析这个算法步骤。
假设需要逆序的单链表为：




则逆序以后的链表为：




首先我们创建一个新结点 current p1，并且让它指向首元结点，即 current p1 = L -> next;
然后我们创建另外一个新结点 pnext p2，用来保存当前节点的下一个节点，即 pnext p2 = current p1 -> next;
current p1 -> next 一旦将值赋给 pnext p2 之后，就可以将其置空，current p1 ->next = NULL;，因为它是倒序后的尾结点，所以为空。
具体请看下图：


经过上面的处理，链表变成下图所示。



这时候我们需要新建一个结点 prev p3 用于保存 pnext p2 -> next，因为这个值将是新链表 current p1 的前驱，所以有语句 prev p3 = pnext p2 -> next。
我们的目的是将 current p1 这个保存当前结点的元素移向后一个结点，同时把pnext也向后一位，其实就是要把 pnext p2 的值赋给 current p1，还有prev p3的值赋给pnext p2，所以可以这样：
  1. 先把pnext p2的值赋给prev p3，即 prev = pnext->next;
  2. 然后用pnext->next保存current的值，即pnext->next = current;
  3. 这个时候current = pnext;就可以把current向后移动一位
  4. 而pnext也可以借机获取prev的值从而也向后移动一位，pnext = prev;
循环一次修改以后的单链表如下：



重复上面循环步骤


循环一次修改以后的单链表如下：


最后将header->next指向 current p1，完成整个单链表的逆序。



让 current 始终保存当前链表当前位置，pnext保存下一个结点位置，重复循环即可。
具体代码为：

01Status ListReverse(LinkList L)
02{
03    LinkList current,pnext,prev;
04    if(L == NULL || L->next == NULL)
05        return L;
06    current = L->next;                           //p1指向链表头节点的下一个节点
07    pnext = current->next;
08    current->next = NULL;
09    while(pnext)
10    {
11        prev = pnext->next;
12        pnext->next = current;
13        current = pnext;
14        pnext = prev;
15    }
16    printf("current = %d,next = %d \n",current->data,current->next->data);
17    L->next = current;                           //将链表头节点指向p1
18    return L;
19}
完整可执行代码：

001#include "stdio.h"
002
003#define OK 1
004#define ERROR 0
005#define TRUE 1
006#define FALSE 0
007
008typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
009typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
010
011typedef struct Node
012{
013    ElemType data;
014    struct Node *next;
015}Node;
016typedef struct Node *LinkList; /* 定义LinkList */
017
018Status visit(ElemType c)
019{
020    printf("%d ",c);
021    return OK;
022}
023
024/* 初始化顺序线性表 */
025Status InitList(LinkList *L)
026{
027    *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
028    if(!(*L)) /* 存储分配失败 */
029            return ERROR;
030    (*L)->next=NULL; /* 指针域为空 */
031
032    return OK;
033}
034
035/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
036int ListLength(LinkList L)
037{
038    int i=0;
039    LinkList p=L->next; /* p指向第一个结点 */
040    while(p)
041    {
042        i++;
043        p=p->next;
044    }
045    return i;
046}
047
048/* 初始条件：顺序线性表L已存在 */
049/* 操作结果：依次对L的每个数据元素输出 */
050Status ListTraverse(LinkList L)
051{
052    LinkList p=L->next;
053    while(p)
054    {
055        visit(p->data);
056        p=p->next;
057    }
058    printf("\n");
059    return OK;
060}
061
062/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
063void CreateListHead(LinkList *L, int n)
064{
065    LinkList p;
066    int i;
067    srand(time(0));                         /* 初始化随机数种子 */
068    *L = (LinkList)malloc(sizeof(Node));
069    (*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
070    for (i=0; i < n; i++)
071    {
072        p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
073        p->data = rand()%100+1;             /*  随机生成100以内的数字 */
074        p->next = (*L)->next;
075        (*L)->next = p;                      /*  插入到表头 */
076    }
077}
078
079/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
080void CreateListTail(LinkList *L, int n)
081{
082    LinkList p,r;
083    int i;
084    srand(time(0));                      /* 初始化随机数种子 */
085    *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
086    r=*L;                                /* r为指向尾部的结点 */
087    for (i=0; i < n; i++)
088    {
089        p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
090        p->data = rand()%100+1;           /*  随机生成100以内的数字 */
091        r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
092        r = p;                            /* 将当前的新结点定义为表尾终端结点 */
093    }
094    r->next = NULL;                       /* 表示当前链表结束 */
095}
096
097/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
098/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
099Status ListDelete(LinkList *L,int i,ElemType *e)
100{
101    int j;
102    LinkList p,q;
103    p = *L;
104    j = 1;
105    while (p->next && j < i)  /* 遍历寻找第i个元素 */
106    {
107        p = p->next;
108        ++j;
109    }
110    if (!(p->next) || j > i)
111        return ERROR;           /* 第i个元素不存在 */
112    q = p->next;
113    p->next = q->next;            /* 将q的后继赋值给p的后继 */
114    *e = q->data;               /* 将q结点中的数据给e */
115    free(q);                    /* 让系统回收此结点，释放内存 */
116    return OK;
117}
118
119Status ListReverse(LinkList L)
120{
121    LinkList current,pnext,prev;
122    if(L == NULL || L->next == NULL)
123        return L;
124    current = L->next;                           //p1指向链表头节点的下一个节点
125    pnext = current->next;
126    current->next = NULL;
127    while(pnext)
128    {
129        prev = pnext->next;
130        pnext->next = current;
131        current = pnext;
132        pnext = prev;
133    }
134    printf("current = %d,next = %d \n",current->data,current->next->data);
135    L->next = current;                           //将链表头节点指向p1
136    return L;
137}
138
139int main()
140{
141    LinkList L;
142    Status i;
143    char opp;
144    ElemType e;
145    int find;
146    int tmp;
147
148    i=InitList(&L);
149    printf("初始化L后：ListLength(L)=%d\n",ListLength(L));
150
151    printf("\n1.查看链表 \n2.创建链表（尾插法） \n3.链表长度 \n4.链表逆序 \n0.退出 \n请选择你的操作：\n");
152    while(opp != '0'){
153        scanf("%c",&opp);
154        switch(opp){
155            case '1':
156                ListTraverse(L);
157                printf("\n");
158                break;
159
160            case '2':
161                CreateListTail(&L,20);
162                printf("整体创建L的元素(尾插法)：\n");
163                ListTraverse(L);
164                printf("\n");
165                break;
166
167            case '3':
168                //clearList(pHead);   //清空链表
169                printf("ListLength(L)=%d \n",ListLength(L));
170                printf("\n");
171                break;
172
173            case '4':
174                //printf("需要删除第几个结点？\n");
175                //scanf("%d", &find);
176                //ListDelete(&L,find,&e);
177                ListReverse(L);
178                ListTraverse(L);
179                printf("\n");
180                break;
181
182            case '0':
183                exit(0);
184        }
185    }
186
187}

延伸阅读

此文章所在专题列表如下：
  1. 结构之美：定义一个线性表
  2. 结构之美：线性表的查找、插入与删除操作
  3. 结构之美：线性表的链式存储结构——链表
  4. 结构之美：单链表的初始化、创建与遍历
  5. 结构之美：单链表的头结点与头指针
  6. 结构之美：使用头插法创建单链表
  7. 结构之美：使用尾插法创建单链表
  8. 结构之美：单链表的销毁删除
  9. 结构之美：查找单链表指定位置结点的数据
  10. 结构之美：在单链表指定位置插入数据
  11. 结构之美：删除单链表指定位置的数据
  12. 结构之美：单链表逆序
  13. 结构之美：判断单链表中是否有环
  14. 结构之美：获取单链表倒数第N个结点值
  15. 单循环链表的初始化、创建、删除、查找与遍历
  16. 结构之美：双向循环链表的结构与定义

本文地址：http://www.nowamagic.net/librarys/veda/detail/1827，欢迎访问原出处。




时间：