剑指offer 链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

思路：设置两个指针，一个指针从链表第一个结点开始，另一个指针从第k个结点开始，两个指针同时走，当第二个指针到达链表尾时，第一个指针指向倒数第k个结点。

考虑特殊情况：链表长度小于k，那么返回空。

btw，通过测试，倒数第0个结点看做链表的最后一个结点。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
12         ListNode *tmp = pListHead, *res = pListHead;
13         /* unsigned int cnt = 0;
14         for (; tmp != NULL; cnt++) {
15             if (cnt >= k)
16                 res = res->next;
17             tmp = tmp->next;
18         }
19         return cnt < k ? NULL : res; */
20         int cnt = 0;
21         while (tmp != NULL && (cnt < k)) {
22             tmp = tmp->next;
23             cnt++;
24         }
25         while (tmp != NULL) {
26             tmp = tmp->next;
27             res = res->next;
28         }
29         return cnt < k ? NULL : res;
30     }
31 };

更新：根据剑指offer原书，最后一个节点，k=1，因此无符号整型k==0是要排除。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
12         if (pListHead == nullptr || k == 0) {
13             return nullptr;
14         }
15         int cnt = 0;
16         ListNode *low = pListHead, *fast = pListHead; 
17         while (fast != nullptr && cnt < k) {
18             fast = fast->next;
19             cnt++;
20         }
21         while (fast != nullptr) {
22             low = low->next;
23             fast = fast->next;
24         }
25         return cnt == k ? low : nullptr;
26     }
27 };

相关题目：求链表的中间节点。如果链表总长度为奇数，则返回中间节点，否则返回中间的任意一个节点。

思路：设置快慢指针，快指针每次走两步，慢指针每次走一步。

 1 ListNode* FindMidNode(ListNode* pListHead) {
 2     if (pListHead == NULL) {
 3         return NULL;
 4     }
 5     ListNode *low = pListNode, *fast = pListNode;
 6     while (fast->next != NULL && fast->next->next != NULL) {
 7         low = low->next;
 8         fast = fast->next->next;
 9     }
10     return low;
11 }