开发者社区> 南尘2251> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

面试 8:快慢指针法玩转链表算法面试(二)

简介: 昨天在最后给大家留了拓展题,不知道大家有没有思考完成,其实南尘说有巨坑是吓大家的啦,实际上也没什么。我们来继续看看昨天这个拓展题。 面试题:给定单链表的头结点,删除单链表的倒数第 k 个结点。
+关注继续查看

昨天在最后给大家留了拓展题,不知道大家有没有思考完成,其实南尘说有巨坑是吓大家的啦,实际上也没什么。我们来继续看看昨天这个拓展题。

面试题:给定单链表的头结点,删除单链表的倒数第 k 个结点。

前面的文章见链接:面试 7:面试常见的链表算法捷径(一)

这个题和前面的文章中增加了一个操作,除了找出来这个结点,我们还要删除它。删除一个结点,想必大家必定也知道:要想操作(添加、删除)单链表的某个结点,那我们还得知道这个节点的前一个节点。所以我们要删除倒数第 k 个结点,就必须要找到倒数第 k+1 个结点。然后把倒数第 k+1 个元素的 next 变量 p.next 指向 p.next.next。

我们找到倒数第 k 个结点的时候,先让 fast 走了 k-1 步,然后再让 slow 变量和 fast 同步走,它们之间就会一直保持 k-1 的距离,所以当 fast 到链表尾结点的时候,slow 刚刚指向的是倒数第 k 个结点。

本题由于我们要知道倒数第 k+1 个结点,所以得让 fast 先走 k 步,待 fast 指向链表尾结点的时候,slow 正好指向倒数第 k+1 个结点。

我们简单思考一下临界值:

  1. 当 k = 1 的时候,删除的值是尾结点。我们让 fast 先走 1 步,当 fast.next 为尾结点的时候,倒数第 k+1 个结点正好是我们的倒数第二个结点。我们删除 slow.next,并让slow.next 指向 slow.next.next = null,满足条件。
  2. 当 k > len 的时候,我们要找的倒数第 k 个元素不存在,直接出错;
  3. 当 1 < k < len 的时候,k 最大为 len-1 的时候,fast 移动 len-1 步,直接到达尾结点,此时,snow 指向头结点。删除倒数第 k 个元素,即删除正数第 2 个结点即可;
  4. 当 k = len 的时候比较特殊,当 fast 移动 len 步的时候,已经指向了 fast.next = null,此时我们其实要删除的是头结点,直接返回 head.next 即可。

所以我们自然能得到这样的代码。

public class Test07 {
    public static class LinkNode {
        int data;
        LinkNode next;

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private static LinkNode delTheSpecifiedReverse(LinkNode head, int k) {
        LinkNode slow = head;
        LinkNode fast = head;
        if (fast == null) {
            throw new RuntimeException("your linkNode is null");
        }
        // 先让 fast 先走 k 步
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                // 说明输入的 k 已经超过了链表长度,直接报错
                throw new RuntimeException("the value k is too large.");
            }
            fast = fast.next;
        }
        // fast == null ,说明已经到了尾结点后面的空区域,说明要删除的就是头结点。
        if (fast == null) {
            return head.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        LinkNode node = delTheSpecifiedReverse(head, 3);
        while (node != null) {
            System.out.print(node.data + "->");
            node = node.next;
        }
    }
}

好了,我们解决了昨天文章中留下的拓展题,今天我们来看看我们链表都还有些怎样的考法。

面试题:定义一个单链表,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。为了方便,我们链表的 data 采用整型。

这是一道反转链表的经典题,我们来屡一下思路:一个结点包含下一结点的引用,反转的意思就是要把原来指向下一结点的引用指向上一个结点。我们可以分为下面的步骤:

  1. 找到当前要反转的结点的下一个结点,并用变量保存,因为下一次要反转的是它,如果我们不保存的话一定会因为前面已经反转,导致无法通过遍历得到这个结点;
  2. 然后让当前结点的 next 引用指向上一个结点,上一个结点初始 null 因为头结点的反转后变成尾结点;
  3. 当前要反转的结点变成下一个要比较元素的上一个结点,用变量保存;
  4. 当前要比较的结点赋值为之前保存的未反转前的下一个结点;
  5. 当前反转的结点为 null 的时候,保存的上一个结点即反转后的链表头结点。

用代码实现就是:

public class Test08 {

    private static class LinkNode {
        int data;
        LinkNode next;

        LinkNode(int data) {
            this.data = data;
        }
    }

    private static LinkNode reverseLink(LinkNode head) {
        // 上一个结点
        LinkNode nodePre = null;
        LinkNode next = null;
        LinkNode node = head;
        while (node != null) {
            // 先用 next 保存下一个要反转的结点,不然会导致链表断裂。
            next = node.next;
            // 再把现在结点的 next 引用指向上一个结点
            node.next = nodePre;
            // 把当前结点赋值给 nodePre 变量,以便于下一次赋值
            nodePre = node;
            // 向后遍历
            node = next;
        }
        return nodePre;
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        LinkNode node = reverseLink(head);
        while (node != null) {
            System.out.print(node.data + "->");
            node = node.next;
        }
    }
}

链表可以考的可真多,相信不是小伙伴都和我一样,云里雾里了,那我们今天就讲到这里,后面还要继续考算法,你,打起精神,别睡着了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
[算法总结] 17 题! BAT面试涉及的链表题都在这里了
本文首发于我的个人博客:尾尾部落 链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。 1. 在 O(1) 时间删除链表节点 题目描述:给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间删除该节点。
1394 0
【SQL 学习】一个面试题
今天面试的时候,问了一个sql编写的题目, 求每门成绩的最高分数的id 以及科目,分数。(当时没有写好,郁闷了,面试官还是很好的,给我讲解了一下!)回到宿舍自己有写了一下,两个方法: SQL> create table test (id int ,subject varchar2(20), score int);表已创建。
458 0
SQL 面试题
有表格如下: create table  worker2s(id int primary key,name varchar(12),department varchar(12),salary int,releaseDay date); id 编码 name 姓名...
1263 0
一道sql面试题的解答
题目:   写出一条Sql语句:     取出表A中第31到第40记录(SQLServer, 以自动增长的ID作为主键,  注意:ID可能不是连续的。)   解答(已测试):   1、假设ID是连续的:     select top 10 * from A where ID not i...
709 0
+关注
南尘2251
南尘,GitHub 和各大 Blog 论坛常客,出身 Android,但不仅仅是 Android。写点技术,也吐点情感。做不完的开源,写不完的矫情,你就听听我吹逼,不会错~
47
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载