原创

【剑指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
正文到此结束
本文目录