[程序员面试题精选100题]9.链表中倒数第k个结点

题目

输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

思路一

因为是单向链表，只有从前往后的指针而没有从后往前的指针。因此我们不能倒序遍历链表，只能正序遍历。假设整个链表有n个结点，那么倒数第k个结点是从头结点开始的第n-k-1个结点（从0开始计数）。我们只需要得到链表中结点的个数n，那我们只要从头结点开始往后走n-k-1步就可以了。 因此这种方法需要遍历链表两次。第一次得到链表中结点个数n，，第二次得到从头结点开始的第n-k-1个结点即倒数第k个结点。时间复杂度为O(n)。

代码

/*————————————* 日期：2015-02-08* 作者：SJF0115* 题目: 9.链表中倒数第k个结点* 来源：程序员面试题精选100题—————————————*/;struct ListNode{int val;ListNode *next;ListNode(int x):val(x),next(NULL){}};class Solution {public:ListNode* FindKthTailNode(ListNode* head,int k) {if(head == nullptr || k < 0){return nullptr;}count = 0;ListNode *p = head;while(p){p = p->next;++count;}(count < k){return nullptr;}pos = count – k;p = head;for(int i = 0;i < pos;++i){p = p->next;}//forreturn p;}};int main(){Solution s;ListNode *head = new ListNode(1);ListNode *node;for(int i = 8;i >= 2;–i){node = new ListNode(i);node->next = head->next;head->next = node;}//forListNode *result = s.FindKthTailNode(head,3);// 输出if(result == nullptr){cout<<“nullptr”<<endl;}//ifelse{cout<<result->val<<endl;};}

思路二

上面那种思路需要两次遍历，如何才能只需一次遍历呢？ 如果我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动， k-1 步开始，第二个指针也开始从链表的头指针开始遍历，两个指针齐头并进。由于两个指针的距离保持在k-1；当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第 K个节点。

代码二

/*————————————* 日期：2015-02-08* 作者：SJF0115* 题目: 9.链表中倒数第k个结点* 来源：程序员面试题精选100题—————————————*/;struct ListNode{int val;ListNode *next;ListNode(int x):val(x),next(NULL){}};class Solution {public:ListNode* FindKthTailNode(ListNode* head,int k) {if(head == nullptr || k < 0){return nullptr;}//ifListNode *p = head,*q = head;// 指针p移动k-1步int index = 1;while(index < k && p != nullptr){p = p->next;++index;}(p == nullptr){return nullptr;}(p->next){p = p->next;q = q->next;}//whilereturn q;}};int main(){Solution s;ListNode *head = new ListNode(1);ListNode *node;for(int i = 8;i >= 2;–i){node = new ListNode(i);node->next = head->next;head->next = node;}//forListNode *result = s.FindKthTailNode(head,8);// 输出if(result == nullptr){cout<<“nullptr”<<endl;}//ifelse{cout<<result->val<<endl;};}

拓展

输入一个单向链表。如果该链表的结点数为奇数，输出中间的结点；如果链表结点数为偶数，输出中间两个结点前面的一个节点。

代码

/*————————————* 日期：2015-02-08* 作者：SJF0115* 题目: 9.2链表中间结点* 来源：程序员面试题精选100题—————————————*/;struct ListNode{int val;ListNode *next;ListNode(int x):val(x),next(NULL){}};class Solution {public:ListNode* FindMidNode(ListNode* head) {if(head == nullptr){return nullptr;}//ifListNode *slow = head,*fast = head;while(fast->next != nullptr && fast->next->next != nullptr){slow = slow->next;fast = fast->next->next;}//whilereturn slow;}};int main(){Solution s;ListNode *head = new ListNode(1);ListNode *node;for(int i = 8;i >= 2;–i){node = new ListNode(i);node->next = head->next;head->next = node;}//forListNode *result = s.FindMidNode(head);// 输出if(result == nullptr){cout<<“nullptr”<<endl;}//ifelse{cout<<result->val<<endl;};}

与其在那里苦苦挣扎，碍于面子硬撑，倒不如微笑着面对，