结构之美：获取单链表倒数第N个结点值

转自：结构之美：获取单链表倒数第N个结点值


这是一个比较常见的面试算法题：一次遍历找链表倒数第n个节点。
通过一次遍历找到单链表中倒数第n个节点，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。
不管是顺数n个还是倒数n个，其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量，我们能够判断倒数第一个节点，因为他的next==NULL。如果我们用两个指针，并保持他们的距离为n，那么当这个线段的右端指向末尾节点时，左端节点就指向倒数第n个节点。
建立两个指针，第一个先走n步，然后第2个指针也开始走，两个指针步伐（前进速度）一致。当第一个结点走到链表末尾时，第二个节点的位置就是我们需要的倒数第n个节点的值。
代码实现如下：

01Status GetNthNodeFromBack(LinkList L, int n, ElemType *e)
02{
03    int i = 0;
04    LinkList firstNode = L;
05    while (i < n && firstNode->next != NULL)
06    {
07        //正数N个节点，firstNode指向正的第N个节点
08        i++;
09        firstNode = firstNode->next;
10        printf("%d\n", i);
11    }
12    if (firstNode->next == NULL && i < n - 1)
13    {
14        //当节点数量少于N个时，返回NULL
15        printf("超出链表长度\n");
16        return ERROR;
17    }
18    LinkList secNode = L;
19    while (firstNode != NULL)
20    {
21        //查找倒数第N个元素
22        secNode = secNode->next;
23        firstNode = firstNode->next;
24        //printf("secNode:%d\n", secNode->data);
25        //printf("firstNode:%d\n", firstNode->data);
26    }
27    *e = secNode->data;
28    return OK;
29}


完整的程序如下：

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 CreateListTail(LinkList *L, int n)
064{
065    LinkList p,r;
066    int i;
067    srand(time(0));                      /* 初始化随机数种子 */
068    *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
069    r=*L;                                /* r为指向尾部的结点 */
070    for (i=0; i < n; i++)
071    {
072        p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
073        p->data = rand()%100+1;           /*  随机生成100以内的数字 */
074        r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
075        r = p;                            /* 将当前的新结点定义为表尾终端结点 */
076    }
077    r->next = NULL;                       /* 表示当前链表结束 */
078    // 创建有环链表
079    //r->next = p;
080}
081
082Status GetNthNodeFromBack(LinkList L, int n, ElemType *e)
083{
084    int i = 0;
085    LinkList firstNode = L;
086    while (i < n && firstNode->next != NULL)
087    {
088        //正数N个节点，firstNode指向正的第N个节点
089        i++;
090        firstNode = firstNode->next;
091        printf("%d\n", i);
092    }
093    if (firstNode->next == NULL && i < n - 1)
094    {
095        //当节点数量少于N个时，返回NULL
096        printf("超出链表长度\n");
097        return ERROR;
098    }
099    LinkList secNode = L;
100    while (firstNode != NULL)
101    {
102        //查找倒数第N个元素
103        secNode = secNode->next;
104        firstNode = firstNode->next;
105        //printf("secNode:%d\n", secNode->data);
106        //printf("firstNode:%d\n", firstNode->data);
107    }
108    *e = secNode->data;
109    return OK;
110}
111
112int main()
113{
114    LinkList L;
115    Status i;
116    char opp;
117    ElemType e;
118    int find;
119    int tmp;
120
121    i=InitList(&L);
122    printf("初始化L后：ListLength(L)=%d\n",ListLength(L));
123
124    printf("\n1.查看链表 \n2.创建链表（尾插法） \n3.链表长度 \n4.获取倒数第N个结点值 \n0.退出 \n请选择你的操作：\n");
125    while(opp != '0'){
126        scanf("%c",&opp);
127        switch(opp){
128            case '1':
129                ListTraverse(L);
130                printf("\n");
131                break;
132
133            case '2':
134                CreateListTail(&L,20);
135                printf("整体创建L的元素(尾插法)：\n");
136                ListTraverse(L);
137                printf("\n");
138                break;
139
140            case '3':
141                //clearList(pHead);   //清空链表
142                printf("ListLength(L)=%d \n",ListLength(L));
143                printf("\n");
144                break;
145
146            case '4':
147                printf("你要查找倒数第几个结点的值？");
148                scanf("%d", &find);
149                GetNthNodeFromBack(L,find,&e);
150                printf("倒数第%d个元素的值为：%d\n", find, e);
151                //ListTraverse(L);
152                printf("\n");
153                break;
154
155            case '0':
156                exit(0);
157        }
158    }
159}

延伸阅读

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

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




时间：