剑指offer - 链表中倒数第k个节点

题目描述

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

思路:

暴力法: 用一个list存放节点,然后取倒数第k个点。 

时间复杂度 O(N)

空间复杂度 O(N)

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

class Solution:
    def FindKthToTail(self, head, k):
        if not head:
            return None
        nodes = [head]
        while head.next:
            head = head.next
            nodes.append(head)
        if k > len(nodes) or k == 0:
            return None
        else:
            return nodes[len(nodes)-k]

优化一下:

用快慢指针,快指针先走k步,然后慢指针再走。等到快指针为None时,慢指针为倒数第k个元素

class Solution:
    def FindKthToTail(self, head, k):
        if not head:
            return None
        quick = head
        slow = head
        while k > 0 and quick:
            quick = quick.next
            k -= 1
        if k > 0:
            return None
        while quick:
            quick = quick.next
            slow = slow.next
        return slow

 

上一篇:WordPress 一键置顶文章插件推荐


下一篇:快速排序