链表中倒数第k个结点

1. 题目形容

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

2. 示例

无

3. 解题思路

应用双指针的办法：

如果在只心愿一次遍历的状况下, 寻找倒数第k个结点, 能够设置两个指针

第一个指针先往前走k-1步, 而后从第k步开始第二个指针指向头结点

而后两个指针一起遍历

当地一个指针指向尾节点的时候, 第二个指针正好指向倒数第k个结点

4. Java实现

/*public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode FindKthToTail(ListNode head,int k) {        // 快指针先走 k-1 步，慢指针指向头节点，两个节点一起走        // 当快指针走到尾，则慢指针找到 倒数 第 k 个节点        if (k <= 0 || head == null){            return null;        }        ListNode fastNode = head;        ListNode slow = head;        for (int i=0; i<k-1; i++){            if (fastNode.next == null){ // 判断是否会越界                return null;            }            fastNode = fastNode.next;        }                while(fastNode.next != null){            slow = slow.next;            fastNode = fastNode.next;        }        return slow;            }}

5. Python实现

# -*- coding:utf-8 -*-# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = None class Solution:    def FindKthToTail(self, head, k):        # write code here        if not head or k <= 0:            return None                 pBehind = head          for i in range(k-1): #找到第 k-1 个结点            if pBehind.next != None:                pBehind = pBehind.next             else:                return None         pHead = head        while pBehind.next != None: # 而后一起往前走            pBehind = pBehind.next             pHead = pHead.next                     return pHead
如果您感觉本文有用，请点个“在看”