题解 | #输出单向链表中倒数第k个结点#

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

http://www.nowcoder.com/practice/54404a78aec1435a81150f15f899417d

方法一:顺序查找

具体做法

最简单直接的方法即为顺序查找,假设当前链表的长度为 n,则我们知道链表的倒数第 k 个节点即为正数第 n - k 个节点,此时我们只需要顺序遍历到链表的第 n - k个节点即为倒数第 k个节点。

我们首先求出链表的长度 n,然后顺序遍历到链表的第 n - k个节点返回即可。 alt

alt

Java代码


import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = Integer.parseInt(sc.next());
            ListNode head = new ListNode(-1);
            ListNode temp = head;
          //生成链表
            for (int i = 0; i < n; i++) {
                ListNode node = new ListNode(sc.nextInt());
                temp.next = node;
                temp = temp.next;
            }
            int k = Integer.parseInt(sc.next());
            if(getKthFromEnd(head.next,k) != null){
                System.out.println(getKthFromEnd(head.next,k).val);
            }
            else{
                System.out.println(0);
            }
            
        }
    }
    public static ListNode getKthFromEnd(ListNode head, int k) {
        int n = 0;
        ListNode node = null;
      //记录有多少节点
        for (node = head; node != null; node = node.next) {
            n++;
        }
      //找倒数第k个
        for (node = head; n > k; n--) {
            node = node.next;
        }

        return node;
    }
}

class ListNode {
    ListNode next;
    int val;
    ListNode(int val) {
        this.val = val;
        next = null;
    }
}

复杂度分析

  • 时间复杂度:O(n)O(n),其中 nn为链表的长度。需要两次遍历。
  • 空间复杂度:O(1)O(1)

方法二:快慢指针

具体方法

快慢指针的思想。将第一个指针 fast 指向链表的第k+1 个节点,第二个指针 slow 指向链表的第一个节点,此时指针fast 与slow 二者之间刚好间隔 k 个节点。此时两个指针同步向后走,当第一个指针fast 走到链表的尾部空节点时,则此时slow 指针刚好指向链表的倒数第k个节点。

首先将 fast 指向链表的头节点,然后向后走k 步,则此时fast 指针刚好指向链表的第k+1 个节点。

首先将slow 指向链表的头节点,同时slow 与fast 同步向后走,当 fast 指针指向链表的尾部空节点时,则此时返回 slow 所指向的节点即可。

alt

Java代码


import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = Integer.parseInt(sc.next());
            ListNode head = new ListNode(-1);
            ListNode temp = head;
          //生成链表 
            for (int i = 0; i < n; i++) {
                ListNode node = new ListNode(sc.nextInt());
                temp.next = node;
                temp = temp.next;
            }
            int k = Integer.parseInt(sc.next());
          //使用快慢指针
            if(getKthFromEnd(head.next,k) != null){
                System.out.println(getKthFromEnd(head.next,k).val);
            }
            else{
                System.out.println(0);
            }
            
        }
    }
  //通过快慢指针搜索 
    public static ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) return null;

        ListNode fast = head,slow = head;

      //快指针先走k步
        for(int i=0;i<k;i++){
            if(fast==null) return fast;
            fast = fast.next;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

class ListNode {
    ListNode next;
    int val;
    ListNode(int val) {
        this.val = val;
        next = null;
    }
}

复杂度分析

  • 时间复杂度:O(n)O(n),其中n n为链表的长度。我们使用快慢指针,只需要一次遍历即可,复杂度为 O(n)O(n)
  • 空间复杂度:O(1)O(1)
华为机试 文章被收录于专栏

本专栏主要用于分享华为机试的题解,希望对大家有所帮助。

全部评论
这题正确的解法是,在遍历到整数第k个时标记头节点,然后标记点和遍历点同时向后走,此时标记点和遍历点永远距离k,当遍历完成后标记点走到倒数第k,直接输出。时间复杂度O(n)
4 回复 分享
发布于 2022-07-29 00:18
fast指针不是放在K-1的节点上么,怎么是k+1
1 回复 分享
发布于 2022-07-18 23:54
这道题就是想考察快慢指针,可以不用引入额外的存储结构如栈,链表一旦构建完成后就不知道链表的长度了,因此方法一不合要求,方法二是标准答案
点赞 回复 分享
发布于 2024-10-23 10:17 北京
为啥 他必须让我加static啊
点赞 回复 分享
发布于 2023-03-22 04:24 广东
不满足第二个要求:(2)构建后要忘记链表长度。
点赞 回复 分享
发布于 2022-04-25 11:17

相关推荐

驼瑞驰_招募评论官版...:把对方打入公司库是吧
点赞 评论 收藏
分享
阿武同学:基本信息保留前面三行,其他的可以全部删掉,邮箱最重要的你没写,主修课程精简到8个以内,实习里面2/3/4都是水内容的,非要写的话建议两到三句话,项目经历排版优化下,自我评价缩到三行
点赞 评论 收藏
分享
评论
45
8
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务