求單項鏈表的倒數第k個節點（只遍歷一次）

單向鏈表求倒數第k個節點我們可以先遍歷一遍找出鏈表的長度，再設置一個指針走（n-k）步可以找到倒數第k個節點。

但是，這需要遍歷兩次，如果只允許遍歷一次我們就可以使用雙指針。設置一個先指針和一個后指針，兩個指針都指向頭節點，先指針先向前走k步，之后兩個指針一起向前移動，直到先指針遍歷出最后一個節點值為null時，后指針指向的就是倒數第k個節點

代碼c語言

typedef struct LNode{int data;struct LNode *next; }//帶頭節點 int find (LNode * head, int k){LNode *p = head->next->next;LNode *pre = head->next;int i = 0;While(p){p=p->next;i++;if(i>k){pre = pre->next;}}if(pre == head)return -1;elsereturn pre->data; }

?

總結

以上是生活随笔為你收集整理的求单项链表的倒数第k个节点（c语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

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