首页 > 试题广场 >

输出单向链表中倒数第k个结点

[编程题]输出单向链表中倒数第k个结点
  • 热度指数：212162 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。

链表结点定义如下： 
struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};
正常返回倒数第k个结点指针，异常返回空指针.
要求：
(1)正序构建链表;
(2)构建后要忘记链表长度。
数据范围：链表长度满足 ， ，链表中数据满足

本题有多组样例输入。




输入描述:
输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值


输出描述:
输出一个整数
示例1

输入

8
1 2 3 4 5 6 7 8
4

输出

5
算法知识视频讲解
添加回答
Python
牛客883262834号头像 牛客883262834号
HJ51 输出单向链表中倒数第k个结点——python3 版本

先参考sample实现一个节点，然后实现一个单向链表
需求：
1. 根据输入，向单链表中，依次添加节点
2. 查找 倒数第 K 个节点 并输出节点内容 
class SingleNode(object):
    """节点"""
    def __init__(self, item):
        self.item = item
        self.next = None


class SingleLinkList(object):
    """单向链表"""
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head == None

    def append(self, item):
        """尾部添加元素"""
        node = SingleNode(item)
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def search_reverse_k(self, k):
        """单向搜索倒数第K个节点，并输出节点内容"""
        if k <= 0:
            print(None)
        else:
            cur = self.head
            for i in range(n - k):
                cur = cur.next
            print(cur.item)

while True:
    try:
        n = int(input())
        ll = SingleLinkList()
        for item in input().split():
            ll.append(item)
        k = int(input())
        ll.search_reverse_k(k)
    except:
        break



发表于 2022-12-16 13:41:16 回复(0)
Python
山岩头像 山岩
python 
# coding: utf-8
class ListNode(object):
    def __init__(self,data =None):
        self.data = data
        self.next_node = None
def func(head,k):
    left,right = head,head
    for i in range(k):
        if right.next_node:
            right = right.next_node
    while right:
        left = left.next_node
        right = right.next_node
    print left.data
    
if __name__ == "__main__":
    import sys
    k = int(sys.stdin.readline().strip())
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)
    node6 = ListNode(6)
    node7 = ListNode(7)
    node8 = ListNode(8)
    node1.next_node = node2
    node2.next_node = node3
    node3.next_node = node4
    node4.next_node = node5
    node5.next_node = node6
    node6.next_node = node7
    node7.next_node = node8
    
    func(node1,k)


发表于 2022-03-26 13:36:09 回复(0)
Python
牛客622181604号头像 牛客622181604号
# 所以跟链表有什么关系
while True:
    try:
        total = int(input())
        head = list(map(int, input().split()))
        k = int(input())
        if k == 0:
            print('0')
        else:
            print(head[-k])
    except:
        break
发表于 2021-04-05 14:07:49 回复(2)
Python
牛客655434568号头像 牛客655434568号
链表和列表不是一个东西把。。。。
链表为啥就过不了
class list_node():
    def __init__(self, key, node=None):
        self.key = key
        self.node = node
    
    def changnode(self, node):
        self.node = node
        
    def get_node(self):
        return self.node

def main():
    while True:
        try:
            num = int(input())
            node_string = input()
            key_value = int(input())
            p_node_value_list = node_string.split(' ')
#             if key_value == 0:
#                 print(0)
#             else:
#                 print(p_node_value_list[num-key_value])
            node_head = list_node(-1)
            tmp_node = node_head
            for node_values in p_node_value_list:
                key_node = int (node_values)
                node = list_node(key_node)
                tmp_node.changnode(node)
                tmp_node = node
            tmp_node = node_head
            list_index = num - key_value + 1
            for i in range(0, list_index):
                tmp_node = tmp_node.get_node()
            print(int(tmp_node.key))
            for i in range(0, num+1):
                tmp_node = node_head.node
                if tmp_node is not None:
                    node_head.node = tmp_node.get_node()
                    tmp_node = None
            if node_head:
                node_head = None
        except:
            break


if __name__ == '__main__':
    main()
发表于 2021-03-01 19:07:41 回复(0)
Python
xman_nb头像 xman_nb
def find_index(nums,num):
    if len(nums)<=1:
        return 0
    return nums[-num]

while True:
    try:
        n , nums , num = input() , input().split() , int(input())
        print(find_index(nums,num))
    except:
        break
发表于 2021-01-12 13:00:51 回复(1)
Python
大溪地渔民头像 大溪地渔民
双指针法 
class Node:
    def __init__(self, v):
        self.value = v
        self.next_node = None
        
        
def gen_list(nums):
    l = Node(nums[0])
    node = l
    for i in range(1, len(nums)):
        node.next_node = Node(nums[i])
        node = node.next_node
    return l


def find_kth(l, k):
    n1, n2 = l, l
    if k == 0:
        return 0
    for _ in range(k):
        if not n2:
            return 0
        n2 = n2.next_node
    while n2:
        n2 = n2.next_node
        n1 = n1.next_node
    return n1.value


while True:
    try:
        n, nums, k = int(input()), list(map(int, input().split())), int(input())
        l = gen_list(nums)
        print(find_kth(l, k))
    except:
        break


发表于 2020-12-17 16:20:34 回复(0)
Python
枫雪镜夜头像 枫雪镜夜
本地编译器完全正确，但是在线测试通过为0，无语了。 
class ListNode(object):
    def __init__(self, m_nKey, m_pNext=None):
        self.data = m_nKey
        self.next = m_pNext


class LinkedList(object):
    def __init__(self):
        self.head = None

    def prepend(self, val):
        new_node = ListNode(val, self.head)
        self.head = new_node


def FindKthToTail(pListHead, k, n_nodes):
    if k==0:
        print(0)
    elif k >= 1 and k <= n_nodes:
        cur = pListHead
        count = 1
        while cur is not None and count < k:
            cur = cur.next
            count += 1
        print(cur.data)
    else:
        print(None)

while (1):
    try:
        n_nodes = int(input())
        val_list = list(map(int, input().split(' ')))
        k = int(input())
        ll = LinkedList()

        for val in val_list:
            ll.prepend(val)

        FindKthToTail(ll.head, k, n_nodes)
    except:
        break



编辑于 2020-08-19 11:55:30 回复(0)
Python
Jubi头像 Jubi
等大佬帮我看看，是格式问题还是代码问题，过不了，但是错误案例跑自测都能过。 
class Node:
    def __init__(self,data=None,next=None):
        self.value = data
        self.next = next
class pList:
    def __init__(self,head=None):
        self.head = head

def inserToEnd(self,data):
    if data == None:
        return None
    node = Node(data)
    if self.head == None:
        self.head = node 
        return node
    current_node = self.head
    while current_node.next is not None:
        current_node = current_node.next
    current_node.next = node
    return node
def findKthToTail(self,l):   
    if l==0: 
        return self.head.value
    else:
        p = self.head
        q = self.head
        for i in range(k-1):
            if p.next is not None:
                p = p.next
            else:
                return None
        while p.next is not None:
            q = q.next
            p = p.next
        
        return q.value
        
        
while True:
    try:
        n = int(raw_input())
        input = list(map(int,raw_input().split(' ')))
        k = int(raw_input())
        if k>n&nbs***bsp;k<0: print None
        else:
            L = pList()
            for i in input:
                inserToEnd(L,i)
            
            print findKthToTail(L,k)
                    
    except:
        break
    



发表于 2020-08-09 19:37:02 回复(1)
Python
桃崽头像 桃崽 

class listnode:
    def __init__(self,x):
        self.next=None
        self.val=x
class llist:
    #创建头结点
    def __init__(self):
        self.head=None
    #创造链表
    def append(self,x):
        temp=listnode(x)
        if not self.head:
            self.head=temp
        else:
            p=self.head
            while p.next:
                p=p.next
            p.next=temp
    #构造两个指针遍历链表
    def findl(self,n):
        if n<1:
            return 0
        res=list1=list2=listnode(0)
        res.next=self.head
        for i in range(n):
            list1=list1.next
        while list1:
            list1=list1.next
            list2=list2.next
        return list2.val
while True:
    try:
        lst=llist()
        n,arr,k=int(input()),input().split(),int(input())
        for i in arr:
            lst.append(i)
        print(lst.findl(k))

编辑于 2020-04-08 01:22:49 回复(0)
Python
朝夕_头像 朝夕_ 
class Node(object):
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    def __init__(self,node=None):
        self._head = node

    def append(self,item):
        node = Node(item)
        if not self._head:
            self._head = node
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node

    def length(self):
        count = 0
        cur = self._head
        while cur:
            count += 1
            cur = cur.next
        return count

    def search(self,item):
        if not self._head:
            return
        else:
            cur = self._head
            count = 0
            while cur:
                if item <= 0&nbs***bsp;item > self.length():
                    return 0
                else:
                    if count == self.length() - item:
                        return cur.elem
                    count += 1
                    cur = cur.next
            return 0
while True:
    try:
        ll = SingleLinkList()
        a,b,c = int(input()),list(map(int,input().split())),int(input())
        for i in b:
            ll.append(i)
        print(ll.search(c))
    except:
        break

编辑于 2020-02-29 13:47:40 回复(2)
Python
lx的流星头像 lx的流星 
while True:
    try:
        n=int(input().strip())
        list1=list(map(int,input().strip().split(' ')))
        #print(list1)
        k=int(input().strip())
        if k!=0:
            result=list1[-k]
            print(result)
        else:
            print(0)
    except:
        break
发表于 2019-07-07 23:01:12 回复(0)
Python
CassielLee头像 CassielLee 
怎么感觉用python很犯规啊，哈哈


	while True:


    try:         n = int(input())         linkedT = list(map(int,input().split()))         k = int(input())         if k == 0:             print (0)         else:             print(linkedT[-k])     except:         break

发表于 2018-08-29 19:57:22 回复(0)
Python
华科平凡头像 华科平凡

python两行解法

while True:
    try:

        a,b,c=input(),input().split(),int(input())
        print(b[-c] if c!=0 else 0)


    except:
        break
发表于 2017-10-04 15:12:42 回复(7)
Python
牛客912300号头像 牛客912300号
#数组非法访问，求大神解释一下原因~~
import sys
for line in sys.stdin:
n=len(line.split())
list1=line.split()
k=sys.stdin.readline()
a=list1[::-1]
res=a[0]
i=0
for each in a:
i=i+1
            if each==k:              
            print(i)
发表于 2016-09-26 19:56:07 回复(0)
提交观点

问题信息

链表 双指针
难度：
14条回答 43227浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号