首页 > 试题广场 >

链表中倒数第k个结点

[编程题]链表中倒数第k个结点

热度指数：1294367 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

示例1

输入

1,{1,2,3,4,5}

输出

{5}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

推荐

Python

人民的名义

Python 设置两个指针，p1，p2，先让p2走k-1步，然后再一起走，直到p2为最后一个时，p1即为倒数第k个节点

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head==None or k<=0:
            return None
        #设置两个指针，p2指针先走（k-1）步，然后再一起走，当p2为最后一个时，p1就为倒数第k个 数
        p2=head
        p1=head
        #p2先走，走k-1步，如果k大于链表长度则返回 空，否则的话继续走
        while k>1:
            if p2.next!=None:
                p2=p2.next
                k-=1
            else:
                return None
#两个指针一起 走，一直到p2为最后一个,p1即为所求
        while p2.next!=None:
            p1=p1.next
            p2=p2.next
        return p1

编辑于 2019-08-13 14:41:34 回复(23)

Python

好心好报

萌新可以请教一个问题吗？

这个题目自己尝试着先用笨办法写了一下提交都是正确的，为啥使用它的自测输入有bug啊。。。。。附代码

# -*- 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
        # 返回的是一个链表节点 所以需要找到相应的指针
        count = 0
        p = head
        while (p):
            count += 1
            p = p.next
        if count<k:
            return None
        tmp = count-k+1
        while(tmp-1>0):
            head = head.next
            tmp = tmp-1
        return head

发表于 2021-02-26 17:31:12 回复(0)

Python

渔舟唱晚2022

python 快慢指针

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        slow = None
        fast = head
        i = 0
        if k == 0:  return None
        while fast:
            i += 1
            if i == k:
                slow = head
            elif i > k:
                slow = slow.next
            fast = fast.next
        return slow

编辑于 2020-11-04 19:35:25 回复(0)

Python

纯真的我求求offer

# -*- 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 head == None and not k:
            return None
        p1,p2 = head,head
        count = 1
        while p2.next != None:
            if count >=k:
                print("p1 "+str(p1.val))
                p1 = p1.next
            #print("p2 "+str(p2.val))
            p2 = p2.next
            count += 1
        if count<k:
            return None
        return p1

count = 1，倒数第一个，两个指针一起移动

count = 2,倒数第二个，p1比p2晚移动一个

count = n,倒数第n个，p1比p2晚移动n-1个

链表长度有三种情况

1. 链表长度小于k

p2到了结尾，p1还没有移动 count<k

2. 链表长度等于k

p2到了结尾，p1在第一个位置，没有移动 count=k

3. 链表长度大于k

p2到了结尾，p1在倒数第k个位置 count>k

编辑于 2020-09-05 20:16:37 回复(0)

Python

苏堤牧

*- 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
        prev = head
        needed = head
        step = 0  
        while prev:
            prev = prev.next 
            if step >= k:
                needed = needed.next
            step += 1
        if step <  k:
            return None
        return needed

发表于 2020-09-03 21:22:33 回复(0)

Python

BJ-2020

一次遍历找出倒数第K个值
使用两个指针
1.第一个向前走k-1步；第二个不动
2.第k步开始，两个指针同时向前遍历直至第一个指针到达末尾，此时第二个恰好位于倒数第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
        # 判断链表是否为空 且K是否超出链表长度
        if head == None or k == 0:
            return None
        pFirst = head
        pSecond = head
        for i in range(k-1):
            pFirst = pFirst.next
        if pFirst == None:
            return None

        while pFirst:

            pFirst = pFirst.next
            if pFirst:
                pSecond = pSecond.next

        return pSecond

发表于 2020-08-30 01:36:20 回复(0)

Python

DDooo

# -*- 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
        list = []
        while head != None:
            list.append(head)
            head = head.next
        if k > len(list)&nbs***bsp;k < 1:
            return None
        return list[-k]

发表于 2020-07-29 17:21:09 回复(0)

Python

sk8_wt

class Solution:
    def FindKthToTail(self, head, k):
        node = head
        count = 0
        while node:
            count += 1
            node = node.next
        if k>count:
            return None
        num = count - k
        node = head
        while num:
            node = node.next
            num -= 1
        return node

发表于 2020-07-18 21:53:58 回复(0)

Python

codercyan

class Solution:
    def FindKthToTail(self, head, k):
        if head is None or k == 0:
            return None
        
        slow = head
        for _ in range(k):
            if head is None:
                return None  # k 大于 链表长度返回 None
            head = head.next
            
        while head:
            head = head.next
            slow = slow.next
            
        return slow

编辑于 2020-07-09 23:24:22 回复(0)

Python

生下来就会跑

class Solution:
    def FindKthToTail(self, head, k):
        if not head:
            self.n=0
            return head
        ht = self.FindKthToTail(head.next, k)
        self.n += 1
        if self.n == k:
            return head
        return ht

发表于 2020-06-25 18:14:54 回复(0)

Python

jianlinp

也可以维护一个最大长度为k的队列，先进先出，遍历完整个链表后输出第一个元素就行了

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        q = []
        while head is not None:
            q.append(head.val)
            if len(q) > k:
                q.pop(0)
            head = head.next
        if len(q) == k:
            return q[0]

发表于 2020-05-30 01:28:48 回复(0)

Python

牛客616122216号

用循环队列感觉比较简单，队列大小为k,访问的每个节点放在[i%k]的位置，当访问到None时，第[i%k]个位置就是倒数第k个结点。

注意边界问题，k大于链长和k小于1的情况返回None。

空间复杂度，用了长度为k的队列：O(1)

时间复杂度，遍历一遍链表: O(n)

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if k<1:
            return None
        l = [None for _ in range(k)]
        n = head
        i = 0
        while n:
            l[i%k] = n
            i+=1
            n = n.next
        if k > i:
            return None
        return l[i%k]

编辑于 2020-05-24 00:28:39 回复(0)

Python

magicloud44

class Solution:
def FindKthToTail(self, head, k):
# write code here
if k == 0:
return None
step = 0
while True:
step += 1
if step == 1:
fast = head
if step > 1:
fast = fast.next
if step == k+1:
slow = head
if step > k+1:
slow = slow.next
if fast == None:
if step > k:
return slow.val

return None

pycharm 可以通过，这边通不过（{'int' object has no attribute 'val'），是啥原因？求大神指教

发表于 2020-04-16 23:13:14 回复(0)

Python

PKU_xiaowei

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        count = 0
        p = head
        while p <> None:
            p = p.next
            count += 1
        if count < k:
            return None
        p = head
        for _ in range(count-k):
            p = p.next
        return p

发表于 2020-03-31 22:13:20 回复(0)

Python

llfgo4it

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        (742)# construct a slide area
        if k<= 0&nbs***bsp;head == None:
            return None
        t ,pk = head, head
        while t!=None:
            if k>0:
                k-=1
            else:
                pk = pk.next
            # k is out
            t = t.next
        if t == None and k == 0:
            return pk
        else:    (3328)# k> len(List)
            return None

如果从头节点开始遍历到尾节点，再倒着往回数太麻烦。可以做一个长度为k的区间滑块，用两个指针定义头尾，当走在前面的指针达到尾节点时，后面的指针指的就是倒数第k个元素。注意的是：有可能k比整个链表都长，要处理一下。

发表于 2020-03-22 21:23:09 回复(0)

Python

accer

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head == None&nbs***bsp;k <= 0:
            return None
        node = head
        for i in range(k-1):
            head = head.next
            if head == None:
                return None
        while head.next != None:
            head = head.next
            node = node.next
        return node

发表于 2020-02-29 22:12:19 回复(0)

Python

牛客447097232号

# -*- coding:utf-8 -*-
"""
注意：
1. 无节点
2. k为0
3. k大于节点个数

使用两个指针headBackup = head，p先走k-1步
1) 能走k-1步吗？ 不能的话说明k大于节点的个数
2）可以走headBackup再跟上
"""
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        if k == 0:
            return None
        if head == None:
            return None
        headBackup = head
        cnt = 0
        while(head.next != None and cnt < k-1):
            head = head.next
            cnt += 1
        if cnt < k -1:
            return None
        else:
            while(head.next != None):
                head = head.next
                headBackup = headBackup.next
            return headBackup

发表于 2020-02-27 00:23:13 回复(0)

Python

朝夕_

class Solution:
    def FindKthToTail(self, head, k):
        if not head&nbs***bsp;not head.next:
            return head
        else:
            count = 0
            cur = head
            ans = []
            while cur:
                ans.append(cur)
                cur = cur.next
                count += 1
        if 0 < k <= len(ans):
            return ans[-k] 
        else:
            return None

发表于 2020-02-25 11:37:10 回复(0)

Python

201905242154668

链表中倒数第k个结点(理论+python实现)

1.理论

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

参考一下其他大佬的思路，自己再介绍一下自己的理解。

分析思路
链表查找从头结点到尾结点查找，因此查找倒数第k个结点，需要从头结点依次查找到倒数第k个位置的结点。

但问题是我们事先不知道链表的总长度n是多少，这就导致不能明确倒数第k个结点该如何确定其边界和位置。

因此，可以采用快慢指针的方式来确定k的位置所在，其思想是：快指针fast先往前走k步，然后快慢一起走，当快指针为none的时候，慢指针slow走到了倒数第k个节点。

原理介绍如下：

假如链表数据元素如下：[15,3,2,4,5,6,7,10,0,9]，其中要求解倒数第k=2个结点。

首先初始化fast、slow指针都为头结点的位置head，即元素15处
接着快指针fast先走k=2步，即fast快指针先走到元素3的位置，此时fast剩下的元素数量就是慢指针从头结点到倒数第K个结点的步数；
最后快fast慢slow指针同时走，当fast指针运行完之后（fast=None），此时慢指针slow也就到倒数第K个结点的位置了。

2.python实现

# -*- 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
        slow,fast=head,head
        #先让快指针走k步，剩下n-k就是倒k的位置
        for i in range(k):
            if not fast:
                return None
            fast=fast.next
        while fast:  
            # 当快指针为空时，慢指针就刚到链表倒K的位置
            slow=slow.next
            fast=fast.next
        return slow

编辑于 2020-02-25 11:31:21 回复(0)