剑指Offer 22. 链表中倒数第k个节点（Easy）

题解

思路

代码

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

class Solution:
    ### 0916 单指针（48 ms，13.4 MB）
    def getKthFromEnd(self, head, k):
        ## 初始化链表长度为0，初始化辅助指针tmp指向链表头部head
        length, tmp = 0, head
        ## 遍历一遍链表，获得链表长度
        while tmp:
            length += 1
            tmp = tmp.next

        ## 让链表指向倒数k个节点
        for _ in range(length-k):
            head = head.next

        return head

    ### 0916 双指针（56 ms，13.3 MB）
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        ## 初始化让头指针former和尾指针latter均指向链表头部head
        former, latter = head, head
        
        ## 先让头指针former前进k步
        for _ in range(k):
            ## 判断k是否大于链表长度
            if not former:
                return
            former = former.next

        ## 再让头指针former和尾指针latter同时移动，直至头指针former移动至越界
        while former:
            former, latter = former.next, latter.next

        ## 最后返回尾指针latter即可
        return latter