【剑指Offer】014——链表中倒数第K个结点 （链表）

题目描述

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

解题思路

经典的双指针法。定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动，从第k步开始，第二个指针也开始从链表的头指针开始遍历，由于两个指针的距离保持在k-1，当第一个指针到达链表的尾节点时，第二个指针刚好指向倒数第k个节点。

关注要点

1. 链表头指针是否为空，若为空则直接返回null
2. k是否为0，k为0也就是要查找倒数第0个节点，由于计数一般是从1开始的，所有输入0没有实际意义，返回null
3. k是否超出链表的长度，如果链表的节点个数少于k，则在指针后移的过程中会出现next指向空指针的错误，所以程序中要加一个判断

其实倒数第k个，也就是顺数第len（链表的长度） - k个。

参考代码

Java

class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k == 0)
            return null;
        ListNode temp = head;
        // 判断k是否超过链表节点的个数，注意是i < k -1,已经不用判断head是否为空
        for (int i = 0; i < k - 1; i++) {
            if (temp.next != null) {
                temp = temp.next;
            } else {
                return null;
            }
        }
        ListNode quick = head; // 快指针，可以理解为记数
        ListNode slow = head;  // 慢指针，走遍所有
        
        // 慢指针到第k个，需要解释一下k-1,索引从0开始，最后一步有.next
        for (int i = 0; i < k - 1; i++) {
            slow = slow.next;
        }
        while (slow.next != null) {
            slow = slow.next;
            quick = quick.next;
        }
        return quick;
    }
}

Python

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        if head == None or k <= 0:
            return None
        temp = head
        for i in range(k-1):
            if temp.next is None:
                return None
            else:
                temp = temp.next
        quick,slow = head, head
        for i in range(k - 1):slow = slow.next
        while slow.next:
            slow = slow.next
            quick = quick.next
        return quick

个人订阅号

image