首页 > 试题广场 >

找出单向链表中的一个节点，该节点到尾指针的距离为K

[编程题]找出单向链表中的一个节点，该节点到尾指针的距离为K

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

找出单向链表中的一个节点，该节点到尾指针的距离为K。链表的倒数第0个结点为链表的尾指针。要求时间复杂度为O(n)。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}
链表节点的值初始化为1，2，3，4，5，6，7。

输入描述:

该节点到尾指针的距离K

输出描述:

返回该单向链表的倒数第K个节点，输出节点的值

示例1

输入

输出

备注:

请自觉实现一个链表，将1到7依次加入链表，然后再寻找倒数第K个节点。要求加节点与找节点的操作复杂度均为O(n)。

算法知识视频讲解

Java

牛客437896676号

import java.util.*;

class ListNode
{
int m_nKey;
ListNode m_pNext = null;
ListNode(int i){this.m_nKey = i;}
}

public class Main{
public static int F(){
ListNode list = new ListNode(0);
ListNode cur = list;
for(int i = 1; i < 8; i++){
cur.m_pNext = new ListNode(i);
cur = cur.m_pNext;
}
int K;
Scanner in = new Scanner(System.in);
K = in.nextInt();
ListNode l1 = list;
ListNode l2 = list;
for(int i = 0; i < K; i++){
l2 = l2.m_pNext;
}
while(l2 != null){
l1 = l1.m_pNext;
l2 = l2.m_pNext;
}
System.out.print(l1.m_nKey);
return 0;
}

public static void main(String[] args){
F();
}

}

这道题的节题思路很多，但是这个是我能想到的一个还算比较思路不错的方式。可以适合于任意长度的一个list，当然题目中设置了7.写的还算顺利，平时的话可以把思路多写一点。

此题还可反转后直接找第k个，也可先求链表总长，然后再n-k等等的这样子。算是一道基础题，但是难点可能在于输入输出也都要自己写，但是比较良心，因为测试用例很松，错误输入报错也没有提，直接过，其实一般还是应该注意一点这些的。简单题。

发表于 2021-02-26 14:58:24 回复(0)

Java

Nakangzi

import java.util.*;
class ListNode{
    int val;
    ListNode next=null;
    ListNode(int val){
        this.val=val;
    }
}

public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        ListNode head=new ListNode(1);
        ListNode p=null;
        p=head;
        p.next=null;
        for(int i=2;i<8;i++){
            ListNode q=new ListNode(i);
            p.next=q;
            p=q;
            p.next=null;
        }
        p=helper(head,sc.nextInt());
        System.out.println(p.val);
    }
    public static ListNode helper(ListNode head,int k){
        ListNode slow=head,fast=head;
        for(int i=0;i<k;i++){
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

发表于 2020-09-02 10:49:10 回复(0)

Java

何止hz

import java.util.Scanner;

/**
 * @Date: 2020-05-05 10:49
 * @version: 1.0
 */
class ListNode{
    ListNode next;
    int val;

    public ListNode(int val) {
        this.val = val;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        ListNode head = new ListNode(1);
        ListNode pre = head;
        ListNode cur;
        for (int i = 2; i <= 7; i++){//初始化
            cur = new ListNode(i);
            pre.next = cur;
            pre = cur;
        }
        ListNode p1 = head, p2 = head;
        while (p1 != null){
            p1 = p1.next;
            k--;//p1先走k步，这样p1走到尾部，p2正好走到倒数第k个
            if (k < 0)
                p2 = p2.next;
        }
        System.out.println(p2.val);
    }
}

发表于 2020-05-05 11:12:13 回复(0)

Java

你的offer对我打了烊

感觉我的解法有点脱裤子放屁🤣🤣🤣

import java.io.*;
 class Node {
     int val;
     Node next;
     Node(int x) {
         val = x;
         next = null;
     }
 }
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Node list1 = new Node(1);
        Node list2 = new Node(2);
        Node list3 = new Node(3);
        Node list4 = new Node(4);
        Node list5 = new Node(5);
        Node list6 = new Node(6);
        Node list7 = new Node(7);
        Node list = list1;
        list1.next = list2;
        list2.next = list3;
        list3.next = list4;
        list4.next = list5;
        list5.next = list6;
        list6.next = list7;
        while(list.next != null){
            if(list.val == (8-n)){
                System.out.println(list.val);
                return;
            }
            list = list.next;
        }
        System.out.println(list.val);
    }
}

发表于 2020-04-24 23:08:48 回复(0)

Java

飒飒的收到Z传说中

import java.util.*;
class ListNode{
    int val;
    ListNode next = null;
    ListNode(int val){
        this.val=val;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        ListNode list = create();
        for(int i=0;i<7-k;i++){
            list=list.next;
        }
        System.out.print(list.val);
    }
    public static ListNode create(){
        ListNode preList=new ListNode(0);
        ListNode list=preList;
        for(int i=0;i<7;i++){
            list.next=new ListNode(i+1);
            list=list.next;
        }
        return preList.next;
    }
}

任意长度的链表倒数k个的方法。

import java.util.*;
class ListNode{
    int val;
    ListNode next = null;
    ListNode(int val){
        this.val=val;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        ListNode list = create(); 
        ListNode lowList = list;
        for(int i=0;i<k;i++){
            list=list.next;
        }
        while(list!=null) {
        	lowList=lowList.next;
        	list = list.next;
        }
        System.out.print(lowList.val);
    }
    public static ListNode create(){
        ListNode preList=new ListNode(0);
        ListNode list=preList;
        while(sc.hasNext()){
            list.next=new ListNode(sc.nextInt());
            list=list.next;
        }
        return preList.next;
    }
}

编辑于 2019-08-28 13:36:22 回复(1)

提交观点

问题信息

C++工程师数组小米集团链表测试开发工程师测试工程师 2019 Java工程师

来自：小米2019秋招测试开...

上传者：小小

难度：

5条回答 121收藏 13123浏览

通过挑战的用户

查看代码

秋招求求捞捞

2022-10-16 17:13:38
牛客12481...

2022-09-20 11:39:00
牛客58475...

2022-09-19 22:28:53
牛客10465...

2022-09-18 11:15:45
牛客92740...

2022-09-14 17:19:21

找出单向链表中的一个节点，该节点到尾指针的距离为K

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题