Java 八道经典面试题之链表题

目录
  • 第一题 移除链表元素
  • 第二题 反转链表
  • 第三题 链表的中心结点
  • 第四题 倒数第k个结点
  • 第五题 合并两个有序链表
  • 第六题 链表分割
  • 第七题 判断是否回文
  • 第八题 相交链表

第一题 移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

输入:head = [1,2,6,3,4,5,6], val = 6

输出:[1,2,3,4,5]

这道题还是比较简单的我们需要让删除的节点的前一个结点指向删除节点的后一个就行。就比如cur.next==cur.next.next;。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode header=new ListNode(-1);
        header.next=head;
        ListNode cur =header;
        while(cur.next!=null){
            if(cur.next.val==val){
                 cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }
        }
return header.next;
    }
}

第二题 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

输入:head = [1,2,3,4,5]

输出:[5,4,3,2,1]

这也是一个简单题,我们还是先弄一个尾结点,因为链表的最后一个结点的下一个是一个null,这道题我们可以通过一次循环让后一个结点的下一个结点指向前一个结点。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre =null;
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }

return pre;
    }
}

第三题 链表的中心结点

给定一个头结点为 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

答:这个也是一个简单题我们需要用到快慢指针,当快指针指完之后,慢的结点肯定是中点比如18 快的可以走9步每次走两步走到18,慢的可以每次走一部走9步。刚好到中点。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode p =head;
        ListNode q =head;
        while(q!=null&&q.next!=null){
            q=q.next.next;
            p=p.next;
        }
return p;

    }
}

第四题 倒数第k个结点

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

输入:

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

复制

返回值:

{5}

答:这道题也是一个简单题,直接简单粗暴的搞出来倒数第k个点的值就行;

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {

        ListNode cur=head;
        ListNode pre=head;
        int count=0;
        int x=0;

        while(cur!=null){

            cur=cur.next;
            count++;
        }
        if(k<0||k>count){
            return null;
        }
        while(pre!=null){
             if(x==count-k){
               break;
            }else{
            pre=pre.next;
            x++;
             }
        }
 return pre;
    }
}

这道题写的有点麻烦了,我们也可以用快慢指针做。一个指针走5步一个走4步。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode p=head;
        ListNode q=head;
       for(int i = 0; i < k; i++) {
           if (p != null) {
            p= p.next;
        } else {
            return null;
        }
    }
        while(p!=null){
            p=p.next;
            q=q.next;
        }
        return q;
    }
}

第五题 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入:l1 = [1,2,4], l2 = [1,3,4]

输出:[1,1,2,3,4,4]

答:这道题考到了怎么将两个链表合并,我们需要将两个链表从大到小合并起来。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        // 任一为空,直接连接另一条链表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return dummyHead.next;
    }
}

第六题 链表分割

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

输入:l1 = [1,2,1,3,2] 3

输出:[1,2,1,2,3]

这道题比较难了需要我们创建两个链表,一个数大与等于x的链表,另一个数小于x的链表。然后让上一个链表的下一个尾结点指向下一个结点的尾巴结点。

这里我们需要用到如何将两个链表合并成一个链表。

做题的时候先想怎么做然后在动手!

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode newHead = new ListNode(0);
        ListNode flagHead = new ListNode(0);
        ListNode newh = newHead;
        ListNode flagh = flagHead;
        while(pHead != null){
            if(pHead.val < x){
                newh.next = new ListNode(pHead.val);
                newh = newh.next;
            }else{
                flagh.next = new ListNode(pHead.val);
                flagh = flagh.next;
            }
            pHead = pHead.next;
        }
        newh.next = flagHead.next;
        return newHead.next;
    }
}

第七题 判断是否回文

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

1->2->2->1

返回:true

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // write code here
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
         ListNode cur=slow.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //3.一个从前往后,一个从后往前  如果相遇,则证明回文
        while(head!=slow){
            if(head.val!=slow.val){//先判断值是否相等
                return false;
            }
            if(head.next==slow){//偶数情况下
                return true;
            }
            head=head.next;
            slow=slow.next;
    }
        return true;
}

第八题 相交链表

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

可以用笨方法就是计算出来每个链表的个数然后让多的先走。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
                ListNode last = headB;
        while (last.next != null) {
            last = last.next;
        }
last.next = headB;

        ListNode fast = headA;
        ListNode slow = headA;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = headA;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                last.next = null;
                return fast;
            }
        }
        last.next = null;
        return null;
    }
}

到此这篇关于Java 八道经典面试题之链表题的文章就介绍到这了,更多相关Java 链表题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java之单链表问题解决案例讲解

    单链表 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据. 问题 问题1:给定一个单链表,判断链表中是否有环 问题2:给定一个链表,返回链表开始入环的第一个节点,如果无环,则返回null class Node{ public int data; Node next; public Node(int da

  • JAVA实现链表面试题

    这份笔记整理了整整一个星期,每一行代码都是自己默写完成,并测试运行成功,同时也回顾了一下<剑指offer>这本书中和链表有关的讲解,希望对笔试和面试有所帮助. 本文包含链表的以下内容: 1.单链表的创建和遍历 2.求单链表中节点的个数 3.查找单链表中的倒数第k个结点(剑指offer,题15) 4.查找单链表中的中间结点 5.合并两个有序的单链表,合并之后的链表依然有序[出现频率高](剑指offer,题17) 6.单链表的反转[出现频率最高](剑指offer,题16) 7.从尾到头打印单链表(

  • 面试题:用 Java 逆序打印链表

    昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 volatile 关键字,不少朋友问我,到底为啥要加 volatile 这个关键字呀,而它,到底又有什么神奇的作用呢? 对 volatile 这个关键字,在昨天的讲解中我们简单说了一下:被 volatile 修饰的共享变量,都会具有下面两个属性: 保证不同线程对该变量操作的内存可见性. 禁止指令重排序. 共享变量:如果一个变量在多个线程的工作内存中都存在副本,那么这个变量就是这几个线程的共享变量. 可见性:一个线

  • Java面试题-实现复杂链表的复制代码分享

    阿里终面在线编程题,写出来与大家分享一下 有一个单向链表,每个节点都包含一个random指针,指向本链表中的某个节点或者为空,写一个深度拷贝函数,拷贝整个链表,包括random指针.尽可能考虑可能的异常情况. 算法如下: /* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.labe

  • Java 八道经典面试题之链表题

    目录 第一题 移除链表元素 第二题 反转链表 第三题 链表的中心结点 第四题 倒数第k个结点 第五题 合并两个有序链表 第六题 链表分割 第七题 判断是否回文 第八题 相交链表 第一题 移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 . 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 这道题还是比较简单的我们需要让删除的节点的前一个结点指向删

  • Linux下C语言的几道经典面试题小结(分享)

    本篇文章整理了几道Linux下C语言的经典面试题,相信对大家更好的理解Linux下的C语言会有很大的帮助,欢迎大家探讨指正. 1.如果在Linux下使用GCC编译器执行下列程序,输出结果是什么? 答案如下: 2.C语言程序不使用任何条件运算符,打印出十次"Hello"? 答案如下: 或是: 3.如果在Linux下使用GCC编译器执行下列程序,输出结果是什么? 答案如下: 4.如果在Linux下使用GCC编译器执行下列程序,输出结果是什么? 答案如下: 5.如果在Linux下使用GCC编

  • Java经典面试题最全汇总208道(一)

    目录 前言 1.JDK 和 JRE 有什么区别? 2.== 和 equals 的区别是什么? 3.final 在 java 中有什么作用? 4.java 中的 Math.round(-1.5) 等于多少? 5.String 属于基础的数据类型吗? 6.String str="i"与 String str=new String(“i”)一样吗? 7.如何将字符串反转? 8.String 类的常用方法都有那些? 9.new String("a") + new Strin

  • Java经典面试题最全汇总208道(五)

    目录 前言 152.什么是 YAML? 153.如何使用 Spring Boot 实现分页和排序? 154.如何使用 Spring Boot 实现异常处理? 155.单点登录 156.Spring Boot比Spring多哪些注解 157.打包和部署 158.Spring Boot如何访问不同的数据库 159.查询网站在线人数 160.easyExcel如何实现 161.什么是 Swagger?你用 Spring Boot 实现了它吗? 162.数据库的三范式是什么? 163.一张自增表里面总共

  • Java经典面试题最全汇总208道(四)

    目录 前言 126.Spring 框架中的单例 Beans 是线程安全的么? 127.请解释 Spring Bean 的自动装配? 129.什么是 Spring Batch? 130.spring mvc 和 struts 的区别是什么? 131.请举例解释@Required 注解? 132.Spring常用注解 133.项目中是如何实现权限验证的,权限验证需要几张表 134.谈谈controller,接口调用的路径问题 135.如何防止表单重复提交 136.Spring中都应用了哪些设计模式

  • Java经典面试题最全汇总208道(三)

    目录 前言 websocket应用的是哪个协议 106.说一下 tcp 粘包是怎么产生的? 107.请列举出在 JDK 中几个常用的设计模式? 108.什么是设计模式?你是否在你的代码里面使用过任何设计模式? 110.在 Java 中,什么叫观察者设计模式(observer design pattern)? 111.使用工厂模式最主要的好处是什么?在哪里使用? 112.请解释自动装配模式的区别? 113.举一个用 Java 实现的装饰模式(decorator design pattern)?它是

  • Java经典面试题最全汇总208道(二)

    目录 前言 53.concurrentHashMap和HashTable有什么区别 54.HasmMap和HashSet的区别 55.请谈谈 ReadWriteLock 和 StampedLock 56.线程的run()和start()有什么区别? 57.为什么我们调用 start() 方法时会执行 run() 方法,为什么我们不能直接调用 run() 方法? 58.Synchronized 用过吗,其原理是什么? 59.JVM 对 Java 的原生锁做了哪些优化? 60.为什么 wait(),

  • Java经典面试题最全汇总208道(六)

    目录 前言 181.什么是类加载器,类加载器有哪些? 182.说一下类加载的执行过程? 183.JVM的类加载机制是什么? 184.什么是双亲委派模型? 185.怎么判断对象是否可以被回收? 186.说一下 jvm 有哪些垃圾回收算法? 187.说一下 jvm 有哪些垃圾回收器? 188.JVM栈堆概念,何时销毁对象 189.新生代垃圾回收器和老生代垃圾回收器都有哪些?有什么区别? 190.详细介绍一下 CMS 垃圾回收器? 191.简述分代垃圾回收器是怎么工作的? 192.Redis是什么?

  • 经典的20道AJAX面试题(必知必会)

    1.什么是AJAX,为什么要使用Ajax(请谈一下你对Ajax的认识) 什么是ajax: AJAX是"Asynchronous JavaScript and XML"的缩写.他是指一种创建交互式网页应用的网页开发技术. Ajax包含下列技术: 基于web标准(standards-basedpresentation)XHTML+CSS的表示: 使用 DOM(Document ObjectModel)进行动态显示及交互: 使用 XML 和 XSLT 进行数据交换及相关操作: 使用 XMLH

  • Python 经典面试题 21 道【不可错过】

    到底什么是Python? •Python是一种解释性语言.Python代码在运行之前不需要编译.其它解释性语言还包括PHP和Ruby. •Python是动态类型语言,指的是在声明变量时,不需要说明变量的类型. •Python非常适合面向对象的编程(OOP),因为它支持通过组合(composition)与继承(inheritance)的方式定义类(class). •Python中没有访问说明符(类似C++中的public和private),这么设计的依据是"大家都是成年人了". 对pyt

随机推荐