第 13 題（鏈表）：
題目：輸入一個單向鏈表，輸出該鏈表中倒數第 k 個結點。鏈表的倒數第 0 個結點為鏈表
的尾指針。
鏈表結點定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};

?

我的思路：先翻轉鏈表，再從翻轉后的鏈表的頭向尾數k-1個，返回，再次翻轉鏈表。

代碼如下：注意這個思路非常差。差的原因是：如果只是用最原始的方法，先遍歷一遍計數，再遍歷一遍找倒數第k個，需要遍歷兩遍。但我的思路，翻轉兩次鏈表就要遍歷兩遍。還要在走k-1步找倒數第k個。繁瑣至極。

/* 第 13 題（鏈表）： 題目：輸入一個單向鏈表，輸出該鏈表中倒數第 k 個結點。鏈表的倒數第 0 個結點為鏈表 的尾指針。 鏈表結點定義如下： struct ListNode { int m_nKey; ListNode* m_pNext; }; start time = 20:40 end time */#include <stdio.h> #include <stdlib.h>typedef struct ListNode {int m_nKey;ListNode* m_pNext; }ListNode;ListNode * reverseList(ListNode * L) {ListNode * pp = L;ListNode * p = L->m_pNext;pp->m_pNext = NULL;while (p != NULL){ListNode * p3 = p->m_pNext;p->m_pNext = pp;pp = p;p = p3;}return pp; }ListNode * getKthNodeFromBack(ListNode * L, int k) {if(k == 0)return NULL;ListNode * rL = reverseList(L);ListNode * p = rL;for (int i = 0; p != NULL && i < k-1; i++) //注意檢測k不能超過鏈表長度，否則返回NULL {p = p->m_pNext;}reverseList(rL);return p; }void displayList(ListNode * L) {ListNode * p = L;while (p != NULL){printf("%d ",p->m_nKey);p = p->m_pNext;}printf("\n"); }void createList(ListNode * &L) {int d;scanf("%d",&d);if (d != 0){L = (ListNode *)malloc(sizeof(ListNode));L->m_nKey = d;L->m_pNext = NULL;createList(L->m_pNext);} }int main() {ListNode * L = NULL;createList(L);ListNode * pk = getKthNodeFromBack(L, 3);displayList(L);return 0; }

?

網上的思路：http://blog.sina.com.cn/s/blog_60c8379d01013z0s.html

分析：使用兩個指針，low，fast，先把fast的指針指向第k個元素，然后low和fast同時向后遍歷，當fast遍歷到結尾時，low正好遍歷到倒數第k個。注意邊界和指針是否為空的檢測，注意k是否超過鏈表長度。

LinkList.h #ifndef LINKLIST_H #define LINKLIST_H #include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std;typedef struct node{ int val; struct node *next; }node,*pNode;pNode CreateLinkList(pNode &T); pNode FindLastKth(pNode T,int k); #endifLinkList.cpp #include "LinkList.h" pNode CreateLinkList(pNode &T){ int ival; cin>>ival; if(ival==0) return NULL; T = (pNode)malloc(sizeof(node)); T->val = ival; T->next = NULL; T->next = CreateLinkList(T->next); return T; } pNode FindLastKth(pNode T,int k){ pNode low=T,fast = T; for(int i=0;i<k&&fast!=NULL;i++){ fast = fast->next; } if(fast == NULL) return NULL; while(fast!=NULL){ fast = fast->next; low = low->next; } return low; }
Main.cpp #include "LinkList.h"void main(){ pNode T; T = NULL; CreateLinkList(T);int k=3; pNode pnode; pnode = FindLastKth(T,k); cout<<pnode->val; system("pause"); }

?

轉載于:https://www.cnblogs.com/dplearning/p/3972226.html

總結

以上是生活随笔為你收集整理的【编程题目】输入一个单向链表，输出该链表中倒数第 k 个结点的全部內容，希望文章能夠幫你解決所遇到的問題。

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