面试题22：链表中倒数第k个节点

题目描述

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

知识点

链表

Qiang的思路V1

看到这个题最先想到的办法就是遍历一遍将所有的节点保存到一个列表中，然后就能直接得到倒数第k个节点了。

# -*- 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
        l=[]
        while head!=None:
            l.append(head)
            head=head.next
        if len(l)<k or k==0:
            return None
        return l[-k]

但是这种方法需要的空间复杂度为O(n)，实在是太浪费空间了。

Qiang的思路V2

因为第一个思路太浪费空间，我就想肯定存在一种不需要额外空间的方法完成这个问题，然后就只能在链表身上动手脚了。

所以我用了两个指针，分别标识当前遍历的位置和距离当前位置的前k个位置。所以只要我在遍历的时候保持两个指针同步移动，那么当第一个指针到达链表最后一个节点时，第二个指针恰恰是需要的节点。

# -*- 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 k==0 or head==None:
            return None
        p=head
        for i in range(1,k):
            if head.next==None:
                return None
            head=head.next
        while head.next!=None:
            head=head.next
            p=p.next
        return p

完美的代码，空间复杂度降了，也不用求长度了，时间效率也提高了。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。