題目

????輸入一個單向鏈表，輸出該鏈表中倒數第 k ?個結點。鏈表的倒數第 0 ?個結點為鏈表的尾指針。

思路

????算是比較簡單的題目了。

????解法一：

????可以先遍歷一遍統計鏈表個數，然后找到倒數第k個的下標再遍歷，這樣時間復雜富比較高

????解法二：

????雙指針聯動，一個指針先跑K個節點，然后兩個指針一起跑，一個指針跑到尾節點時另一個指針恰好是倒數第K個節點。

include "stdio.h" #include "stdlib.h" //鏈表長度 #define N 50//鏈表節點定義 typedef struct node {int date;struct node * next; }link;link * lastK(link * head,int k);int main(void) {link * head, *p;int i;//隨機數種子 srand((unsigned int)time(0));//生成鏈表head = p = (link *)malloc(sizeof(link));head-> date = rand()%101;head-> next = NULL;for(i=1;i<N;i++){p = p->next = (link *)malloc(sizeof(link));p->date = rand()%101;p->next = NULL;}//輸出鏈表for(p = head;p;p=p->next)printf("%d ",p->date);//產生Ki = rand()%100;printf("\n隨機生成一個K：%d",i); //輸出倒數第K個數p = lastK(head,i);if(p == NULL) printf("錯誤！\n");elseprintf("\n倒數第%d個數是%d\n",i,p->date); }link * lastK(link * head,int k) {link * p,* q;p = q = head;if(k<=0) return NULL;//兩個指針，q先跑個保證p最后指向的是倒數第K個while(k-1 > 0){if(q->next!=NULL)q = q->next;elsereturn NULL;k--;}while(q->next != NULL){p = p->next;q = q->next;}return p; }

總結

以上是生活随笔為你收集整理的输出链表倒数第K个节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。