結構之美:獲取單鏈表倒數第N個結點值

距離——標尺的方法
服務器君一共花費了215.037 ms進行了6次數據庫查詢,努力地為您提供了這個頁面。
試試閱讀模式?希望聽取您的建議

這是一個比較常見的面試算法題:一次遍歷找鏈表倒數第n個節點。

通過一次遍歷找到單鏈表中倒數第n個節點,鏈表可能相當大,可使用輔助空間,但是輔助空間的數目必須固定,不能和n有關。

不管是順數n個還是倒數n個,其實都是距離-標尺問題。標尺是一段距離可以用線段的兩個端點來衡量,我們能夠判斷倒數第一個節點,因為他的next==NULL。如果我們用兩個指針,并保持他們的距離為n,那么當這個線段的右端指向末尾節點時,左端節點就指向倒數第n個節點。

建立兩個指針,第一個先走n步,然后第2個指針也開始走,兩個指針步伐(前進速度)一致。當第一個結點走到鏈表末尾時,第二個節點的位置就是我們需要的倒數第n個節點的值。

代碼實現如下:

Status GetNthNodeFromBack(LinkList L, int n, ElemType *e)
{
    int i = 0;
    LinkList firstNode = L;
    while (i < n && firstNode->next != NULL)
    {
        //正數N個節點,firstNode指向正的第N個節點
        i++;
        firstNode = firstNode->next;
        printf("%d\n", i);
    }
    if (firstNode->next == NULL && i < n - 1)
    {
        //當節點數量少于N個時,返回NULL
        printf("超出鏈表長度\n");
        return ERROR;
    }
    LinkList secNode = L;
    while (firstNode != NULL)
    {
        //查找倒數第N個元素
        secNode = secNode->next;
        firstNode = firstNode->next;
        //printf("secNode:%d\n", secNode->data);
        //printf("firstNode:%d\n", firstNode->data);
    }
    *e = secNode->data;
    return OK;
}

完整的程序如下:

#include "stdio.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;/* Status是函數的類型,其值是函數結果狀態代碼,如OK等 */
typedef int ElemType;/* ElemType類型根據實際情況而定,這里假設為int */

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定義LinkList */

Status visit(ElemType c)
{
    printf("%d ",c);
    return OK;
}

/* 初始化順序線性表 */
Status InitList(LinkList *L)
{
    *L=(LinkList)malloc(sizeof(Node)); /* 產生頭結點,并使L指向此頭結點 */
    if(!(*L)) /* 存儲分配失敗 */
            return ERROR;
    (*L)->next=NULL; /* 指針域為空 */

    return OK;
}

/* 初始條件:順序線性表L已存在。操作結果:返回L中數據元素個數 */
int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next; /* p指向第一個結點 */
    while(p)
    {
        i++;
        p=p->next;
    }
    return i;
}

/* 初始條件:順序線性表L已存在 */
/* 操作結果:依次對L的每個數據元素輸出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

/*  隨機產生n個元素的值,建立帶表頭結點的單鏈線性表L(尾插法) */
void CreateListTail(LinkList *L, int n)
{
	LinkList p,r;
	int i;
	srand(time(0));                      /* 初始化隨機數種子 */
	*L = (LinkList)malloc(sizeof(Node)); /* L為整個線性表 */
	r=*L;                                /* r為指向尾部的結點 */
	for (i=0; i < n; i++)
	{
		p = (Node *)malloc(sizeof(Node)); /*  生成新結點 */
		p->data = rand()%100+1;           /*  隨機生成100以內的數字 */
		r->next=p;                        /* 將表尾終端結點的指針指向新結點 */
		r = p;                            /* 將當前的新結點定義為表尾終端結點 */
	}
	r->next = NULL;                       /* 表示當前鏈表結束 */
	// 創建有環鏈表
    //r->next = p;
}

Status GetNthNodeFromBack(LinkList L, int n, ElemType *e)
{
    int i = 0;
    LinkList firstNode = L;
    while (i < n && firstNode->next != NULL)
    {
        //正數N個節點,firstNode指向正的第N個節點
        i++;
        firstNode = firstNode->next;
        printf("%d\n", i);
    }
    if (firstNode->next == NULL && i < n - 1)
    {
        //當節點數量少于N個時,返回NULL
        printf("超出鏈表長度\n");
        return ERROR;
    }
    LinkList secNode = L;
    while (firstNode != NULL)
    {
        //查找倒數第N個元素
        secNode = secNode->next;
        firstNode = firstNode->next;
        //printf("secNode:%d\n", secNode->data);
        //printf("firstNode:%d\n", firstNode->data);
    }
    *e = secNode->data;
    return OK;
}

int main()
{
    LinkList L;
    Status i;
    char opp;
    ElemType e;
    int find;
    int tmp;

    i=InitList(&L);
    printf("初始化L后:ListLength(L)=%d\n",ListLength(L));

    printf("\n1.查看鏈表 \n2.創建鏈表(尾插法) \n3.鏈表長度 \n4.獲取倒數第N個結點值 \n0.退出 \n請選擇你的操作:\n");
    while(opp != '0'){
        scanf("%c",&opp);
        switch(opp){
            case '1':
                ListTraverse(L);
                printf("\n");
                break;

            case '2':
                CreateListTail(&L,20);
                printf("整體創建L的元素(尾插法):\n");
                ListTraverse(L);
                printf("\n");
                break;

            case '3':
                //clearList(pHead);   //清空鏈表
                printf("ListLength(L)=%d \n",ListLength(L));
                printf("\n");
                break;

            case '4':
                printf("你要查找倒數第幾個結點的值?");
                scanf("%d", &find);
                GetNthNodeFromBack(L,find,&e);
                printf("倒數第%d個元素的值為:%d\n", find, e);
                //ListTraverse(L);
                printf("\n");
                break;

            case '0':
                exit(0);
        }
    }
}

延伸閱讀

此文章所在專題列表如下:

  1. 結構之美:定義一個線性表
  2. 結構之美:線性表的查找、插入與刪除操作
  3. 結構之美:線性表的鏈式存儲結構——鏈表
  4. 結構之美:單鏈表的初始化、創建與遍歷
  5. 結構之美:單鏈表的頭結點與頭指針
  6. 結構之美:使用頭插法創建單鏈表
  7. 結構之美:使用尾插法創建單鏈表
  8. 結構之美:單鏈表的銷毀刪除
  9. 結構之美:查找單鏈表指定位置結點的數據
  10. 結構之美:在單鏈表指定位置插入數據
  11. 結構之美:刪除單鏈表指定位置的數據
  12. 結構之美:單鏈表逆序
  13. 結構之美:判斷單鏈表中是否有環
  14. 結構之美:獲取單鏈表倒數第N個結點值
  15. 單循環鏈表的初始化、創建、刪除、查找與遍歷
  16. 結構之美:雙向循環鏈表的結構與定義

本文地址:http://www.zqhthc.tw/librarys/veda/detail/1840,歡迎訪問原出處。

不打個分嗎?

轉載隨意,但請帶上本文地址:

http://www.zqhthc.tw/librarys/veda/detail/1840

如果你認為這篇文章值得更多人閱讀,歡迎使用下面的分享功能。
小提示:您可以按快捷鍵 Ctrl + D,或點此 加入收藏

閱讀一百本計算機著作吧,少年

很多人覺得自己技術進步很慢,學習效率低,我覺得一個重要原因是看的書少了。多少是多呢?起碼得看3、4、5、6米吧。給個具體的數量,那就100本書吧。很多人知識結構不好而且不系統,因為在特定領域有一個足夠量的知識量+足夠良好的知識結構,系統化以后就足以應對大量未曾遇到過的問題。

奉勸自學者:構建特定領域的知識結構體系的路徑中再也沒有比學習該專業的專業課程更好的了。如果我的知識結構體系足以囊括面試官的大部分甚至吞并他的知識結構體系的話,讀到他言語中的一個詞我們就已經知道他要表達什么,我們可以讓他坐“上位”畢竟他是面試官,但是在知識結構體系以及心理上我們就居高臨下。

所以,閱讀一百本計算機著作吧,少年!

《JavaScript高級程序設計(第2版)》 尼古拉斯·澤卡斯(Nicholas C.Zakas) (作者), 李松峰 (譯者), 曹力 (譯者)

《JavaScript高級程序設計(第2版)》在上一版基礎上進行了大幅度更新和修訂,融入了近幾年來JavaScript應用發展的最新成果,幾乎涵蓋了所有需要理解的重要概念和最新的JavaScript應用成果。從頗具深度的JavaScript語言基礎到作用域(鏈),從引用類型到面向對象編程,從極其靈活的匿名函數到閉包的內部機制,從瀏覽器對象模型(BOM)、文檔對象模型(DOM)到基于事件的Web腳本設計,從XML(E4X)到Ajax及JSON,從高級前端開發技術到前沿的客戶端存儲,從最佳編程實踐到即將成為現實的API,直至JavaScript未來的發展,全景式地展示了JavaScript高級程序設計的方方面面。

更多計算機寶庫...

英超直播吻球网