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

电玩女神 2022-11-30 01:35 60阅读 0赞

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

### 文章目录 ###

*   *  1. 题目（LeetCode 面试题）
     *  2. 解答过程
     *  3. 题目解答
     *   *  (1) C++ 示例
         *  (2) Python 示例

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

--------------------

## 1. 题目（LeetCode 面试题） ##

**原题：**

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

**示例：**

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

**说明：** 给定的 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;
        }
    };

### (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

**运行结果：**  
![在这里插入图片描述][20200822183140600.PNG_pic_center]

[AI]: https://blog.csdn.net/wjinjie
[04]: https://blog.csdn.net/wjinjie/article/details/106523294
[20200822183140600.PNG_pic_center]: /images/20221124/a77ca1d0b0c347db87dd5b3324e4ae70.png