22
- 首先想到暴力方法，先get到链表的长度n
- 然后遍历找到第n-k个结点
- 时间复杂度O(n)，空间复杂度O(1)
int searchK(LinkList L, int k) { // 1.获取链表长度n int n = 0; LNode *p = L->link; while (p != NULL) { p = p->link; n++; } // 2.没有那么多结点，直接返回0 if (n < k) return 0; // 3.遍历找到第n-k个结点 int count = n - k; p = L->link; while (count--) { p = p->link; } cout << "倒数第" << k << "个结点值为" << p->data << endl; return 1; } 复制代码
- 最优肯定要一次遍历解决，自然而然想到双指针也是快慢指针
- 既然要找到第n-k个结点，我们可以先让前一个指针走k步
- 然后两个指针同步走，等到前一个指针走到结尾，后一个指针自然就走到了n-k结点处
- 时间复杂度O(n)，空间复杂度O(1)
int searchK2(LinkList L, int k) { // 1.双指针 LNode *p1 = L->link, *p2 = L->link; int count = 0; while (p1 != NULL) { if (count < k) count++; else p2 = p2->link; // 2.p1走了k步之后，开始同步走 p1 = p1->link; // 3.一直走到链表尾 } // 3.查找成功就输出并返回1 if (count < k) return 0; else { cout << "倒数第" << k << "个结点值为" << p2->data << endl; return 1; } } 复制代码
- 当然也有一些其他的奇淫巧计
- 在我们学了栈之后，利用它的“后进先出”的特性，先把所有值压入栈中，再弹出k个元素，最后一个出栈元素即所求值
- 如果你对递归足够了解，你也可以尝试使用递归解决这个问题
- 终止条件就是遍历结点为空，触底反弹，往回走的过程中记录走过的结点，达到k就是倒数第k个结点，直接返回即可
- 如果没有达到k，直接返回NULL即可
