【每日一题】链表系列(1) —— 返回倒数第k个结点

写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我热爱AI、热爱分享、热爱开源！ 这博客是我对学习的一点总结与思考。如果您也对 深度学习、机器视觉、算法、C++、Python 感兴趣，可以关注我的动态，我们一起学习，一起进步~
我的博客地址为：【AI 菌】的博客

温馨提示：如果您对链表的结构还不了解，建议先加一个餐：【算法与数据结构 04】多图讲解——线性表、顺序表、链表

1. 题目（LeetCode 面试题）

原题：

实现一种算法，找出单向链表中倒数第 k 个结点。返回该结点的值。

  

 

  
1
 

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4

  

 

  
1
  
2
 

说明： 给定的 k 保证是有效的。

2. 解答过程

头脑风暴：
对于找倒数第k个结点的问题，常规思想是：从后向前朝，数到第k个元素即可。但是，单向链表只能循环后移，所以这里我们需要用到一种新的方法——双指针。

所谓双指针，就是设置前、后两个指针都先指向头结点。后指针先移动到第k个结点，那么此时前、后指针相距k个位置。同步后移，当后指针指向链尾时，前指针就自然指向倒数第k个结点。

解答步骤：
根据上面的方法，我们可以将整个解答过程细分为3个简单的步骤：

1. 初始化两个指针：前指针p1和后指针p2，且开始都指向头结点。
2. 保持p1不变，先将p2移动到第k个结点，这时前、后指针相距k个位置。
3. 同时向后移动p1和p2，当后指针指向链尾时，前指针就自然指向倒数第k个结点。

3. 题目解答

下面，我们就将上文中的解答步骤写成代码形式！

(1) C++ 示例

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public: int kthToLast(ListNode* head, int k) { if(head == NULL)  //判断头指针不为空 return 0; ListNode *p1 = head; //前指针 ListNode *p2 = head; //后指针 int i = 0; //i用来确保后指针移到第k个位置 while(i<k){ if(p2 == NULL) return 0; p2 = p2->next; i++; } //相距K个，同步移动，直到后指针到链表尾部。 while(p2 != NULL){ p1 = p1->next; p2 = p2->next; } return p1->val; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

(2) Python 示例

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object): def kthToLast(self, head, k): """ :type head: ListNode :type k: int :rtype: int """ # 初始化前结点p1、后结点p2 p1 = head p2 = head # 移动后结点到第k个位置 for i in range(k): p2 = p2.next # 同时移动前、后结点，直至后结点指向链尾 while p2: p1 = p1.next p2 = p2.next return p1.val 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

运行结果：

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/108171197