小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

[Java]手撕链表面试题及双向链表(进阶)_java 双向链表面试问题

作者：小蓝xlanll | 2024-06-02 07:19:04

踩

java 双向链表面试问题

目录

前言

一.链表面试题

1. 删除链表中等于给定值 val 的所有节点。

2. 反转一个单链表。

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

4. 输入一个链表，输出该链表中倒数第k个结点。

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

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

7. 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

8. 链表的回文结构。(进阶)

9. 输入两个链表，找出它们的第一个公共结点。

10. 给定一个链表，判断链表中是否有环。

11. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null (进阶)

二.无头双向链表的实现

1.基本类的配置:

2.基本功能实现:

1)打印链表:

2)获取链表的长度:

3)链表中是否包含某个元素:

4)找到要删除或插入的元素:

1)头插法:

2)尾插法:

3)任意位置插:

4)删除第一次出现的元素(key):

5)删除所有出现过的元素(key):

6)清空链表:

总结

前言

Hellow,大家好!我是Node_Hao!熟练掌握顺序表及链表的相关操作之后,便可以适当用一些较高难度的链表笔试题巩固提高自己的知识水平,不仅是对原有知识的复习提升,更是打破自己知识舒适区的最佳方式.另外本章还会讲到双向链表的相关知识,毕竟Java的集合框架库中LinkedList底层实现就是无头双向循环链表.所以双向链表的重要性不言而喻.

一.链表面试题

1. 删除链表中等于给定值 val 的所有节点。

解题步骤:

这道题的做法类似于侦查兵探路,首先我们定义一个prev节点和cur节点,prev节点类似长官拥有删除功能,cur类似于士兵只负责探路,有危险(要删的元素)cur向前走,prev长官的指向直接跳过该元素,当cur发现安全(没有要删的元素时),prev再向前挪动.


public ListNode removeAllKey(int key) {
        if (head == null) {
            System.out.println("单链表不能为空!");
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == key) {
            head = head.next;
        }
        return head;
    }

2. 反转一个单链表。

由于链表得天独厚的优势,反转链表只需要改变其各个元素的指向即可,首先我们定义三个变量,三个变量各自有其作用,prev用于充当新的头结点,cur用于改变链表的指向,curNext用于cur向后移动遍历链表,因为cur在其改变指向的同时会丢失向后走的能力.三个变量的步频始终一致,当cur==null时prev刚好走到末尾成为新的头结点.
public ListNode reverseList() {
        if (head == null) {
            return null;
        }
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;//新的头结点
    }

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

这道题如果只是简单的将链表个数除以二,需要遍历链表两次,那么它必然达不到面试的难度,在面试难度下我们只能将链表遍历一次.因此我们需要用快慢指针来解决这类问题,首先定义快指针fast和慢指针slow,假设一个链表长为5,fast的速度为slow的两倍,那么相同时间内fast的路程必然是slow两倍,因此当fast走到末尾时,slow刚好走到中间位置.最后返回slow即可.那么就会产生一个问题,当链表长度为奇数是必然返回中间位置,那如果链表为偶数时,该返回什么位置呢?题目中要求的是返回第二个节点,如果面试官要求返回第一个呢?其实很简单我们只需要让fast在走的过程中为空时,不然slow继续走直接返回slow即可.
 public ListNode middleNode() {
        ListNode faster = head;
        ListNode slower = head;
        while (faster != null && faster.next != null) {
            faster = faster.next.next;
            slower = slower.next;
        }
        return slower;
    }
public ListNode middleNode() {
        ListNode faster = head;
        ListNode slower = head;
        while (faster != null && faster.next != null) {
            faster = faster.next.next;
            if (faster==null){
                return slower;
            }
            slower = slower.next;
        }
        return slower;
    }

4. 输入一个链表，输出该链表中倒数第k个结点。

一看到这道题我们第一时间想到的肯定是,算出链表的长度size,然后减去k,走size-k步即可,这样的话我们需要遍历链表两次.而面试难度只允许你遍历一次.此时就需要一点点数学技巧,咋们结合我下面给出的图来看.倒数第k个节点距最后一个节点k-1步,如果fast先走k-1步,那么slow与fast就相差k-1步,fast与slow一人一步走,当fast为最后一个节点时,slow自然而然就是倒数第k个节点,,此时返回slow即可.但是当我们判读k的合法性时,如果想让k不超过链表的长度我们必须遍历链表,这样就得遍历两次链表了.其实我们可以不判断k是否超过链表大小,只需要在fast移动过程中加一条循环条件,一但fast为空直接返回slow即可.
public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        if (k <= 0) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (k - 1 != 0 && fast != null) {
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            k--;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

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

这道题,需要两个链表不断的比较,所以两个链表的头结点需要不断后移达到比较的效果,因此我们需要一个虚拟的头写点(傀儡节点),让之后较小的数连在它后面.当我们合并完所有节点时,只需返回虚拟头节点的下一个节点即可.


public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode newHead = new ListNode(-1);//虚拟节点
        ListNode tmp = newHead;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tmp.next = head1;
                tmp = tmp.next;
                head1 = head1.next;
            } else {
                tmp.next = head2;
                tmp = tmp.next;
                head2 = head2.next;
            }
        }
        if (head1 == null) {
            tmp.next = head2;
        }
        if (head2 == null) {
            tmp.next = head1;
        }
        return newHead.next;
    }
 
}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

这道题需要将链表分为两个部分,所以我们定义四个变量,bs,be,as,ae,分别是前半段的首尾和后半段的首尾 .经过判断依次将链表元素放入对于位置,最后再将两个链表合并.这道题有很多需要注意的情况:1.题中并没有说链表是有序排序的,所以当后半段不为空时,可能指针域为空的节点不在最后一位,所以我们需要将ae(最后一位手动置空).2.一定不要忘记链接前后两段.3.当前半段为空时直接返回后半段as即可.


public ListNode partition(ListNode pHead, int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while (cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs = cur;
                    be = cur;
                }else {//尾插
                    be.next = cur;
                    be = be.next;
                }
            }else {
                if(as==null){
                    as = cur;
                    ae = cur;
                }else {//尾插
                    ae.next = cur;
                    ae  =ae.next;
                }
            }
            cur = cur.next;
        }
        //预防第一个段为空
        if (bs == null) {
            return as;
        }
        be.next = as;//前后两段链接
        //不一定所有的数字都大于k
        if (as != null) {
            ae.next = null;
        }
        return bs;
    }

7. 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

这道题由于头结点也可能和下一个节点重复,所以需要一个虚拟的头结点,删除思想类似于第一题的侦察兵,cur在前面探路,prev负责删除.值得注意的是,当我们写cur向前走的循环条件时,一定要首先判断cur.next!=null,否则当判断cur.val==cur.next.val时会空指针异常.


public ListNode deleteDuplication(ListNode pHead) {
        if(pHead==null){
            return null;
        }
        ListNode newHead = new ListNode(-1);
        ListNode prev = newHead;
        ListNode cur = pHead;
        while (cur!=null){
            if(cur.next!=null&&cur.val==cur.next.val){
                while (cur.next!=null&&cur.val==cur.next.val){
                    cur = cur.next;
                }
                cur = cur.next;
            }else {
                prev.next = cur;
                prev = prev.next;
                cur = cur.next;
            }
        }
        prev.next = null;
        return newHead.next;
    }

8. 链表的回文结构。(进阶)

这道题堪称经典一题更比三题强,被许多大厂当做面试题,有多种不同的解法,今天我分享的是一种较为容易理解的做法.做法可以概括为三句话"1.找到中间节点,2.反转后半段,3.首尾中间靠拢并判断"1.找到中间节点我们之前已经讲过,用快慢指针这里不过多赘述.2.反转后半段之前也讲过,就是逆置链表的思想.3.首尾中间靠拢并判断是否相等,此时需要注意的是当链表为偶数时,首尾就不会汇聚到同一个节点上,所以我们需要判断当head.next==slow时也跳出循环.


 public boolean chkPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode cur = slow.next;
 
        while (fast != null && fast.next != null) {//找到中间位置
            fast = fast.next.next;
            slow = slow.next;
        }
        while (cur != null) {//反转链表
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        while (head != slow) {//判断回文
            if (slow.val != head.val) {
                return false;
            }
            if (head.next != slow) {
                return true;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }

9. 输入两个链表，找出它们的第一个公共结点。

基于链表各个元素之间靠指针域链接的特性,两个链表之所以能够相交,一定是因为指针域相同.一但相交后面就不可能分开,所以链表相交一定是Y型.但是两个链表的长度不一定相同,所以如果我们想找到相同的节点还是得依靠快慢指针,那么快指针比慢指针多走几步呢?由图我们可以发现两个链表的后半段长度一定相等,差别就在前半段.所以我们可以分别计算出两个链表的长度,让快指针先走两个链表的长度的差值步,此时快慢指针所指向的长度一致,然后一人一步走直到相遇,返回相遇节点即可.

这道题代码看似很长,其实大部分都是计算长度,为了尽可能的少遍历链表,我先假设headA为最长的链表而pl始终指向最长的链表,当计算出的长度小于0时,我们只需交换pl和ps的指向即可.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode pl = headA;
        ListNode ps = headB;
        int len1 = 0;
        int len2 = 0;
        while (pl!=null){
            len1++;
            pl = pl.next;
        }
        pl = headA;
        while (ps!=null){
            len2++;
            ps = ps.next;
        }
        ps = headB;
        int len = len1-len2;
        if(len<0){
            pl = headB;
            ps = headA;
            len = len2 -len1;
        }
        while (len!=0){
            pl = pl.next;
            len--;
        }
        while (pl!=ps){
            if(pl==null||ps==null){
                return null;
            }
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }

10. 给定一个链表，判断链表中是否有环。

这道较为简单,它的作用是为下一道题打基础.判断一个链表是否有环,只需定义两个快慢指针,快指针一次走2步,慢指针一次走1步.如果两个指针能相遇那么一定存在环.如果fast在走的过程中为空那么一定不存在环.
public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null&&fast.next == null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
 
    }

11. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null (进阶)

这道题略有难度,在上一题的基础上我们可以求得相遇点,由我在下图中的分析可得,让fast从起点开始,slow从相遇点开始,一人一步走,一定会在入口点相遇.此时返回入口点即可.


public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;//或者fast
 
    }

二.无头双向链表的实现

无头双向链表作为,java集合框架中LinkedList的底层实现原理,其重要性不言而喻.今天我们就从最底层的逻辑来构建一个无头双向链表,并实现其基本的增删改查功能.

1.基本类的配置:

根据双向链表的基本特性,首先我们要定义定义两个基本类,一个是节点类,一个链表类.节点类中存放双向链表节点的基本属性(值域,前驱,后继),这是其面向对象的第一步.其次我们要在链表类中定义一个头结点和为节点,此时的头结点和尾结点只是一个变量,并不是真实存在.这就体现了无头双向链表的特点.最后我们只需要在链表类中构造自己需要的方法即可.


class ListNode2 {
    public int val;
    public ListNode2 prev;
    public ListNode2 next;
 
    public ListNode2(int val) {
        this.val = val;
    }
}
 
public class My_DoubleList {
    public ListNode2 head;
    public ListNode2 last;
}

2.基本功能实现:

1)打印链表:

定义一个节点类型的变量,在遍历链表的同时打印链表的值即可.


public void display() {
        ListNode2 cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

2)获取链表的长度:

定义一个节点类型的变量和一个计数器,遍历链表的同时计数器加一即可.


public int size() {
        ListNode2 cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

3)链表中是否包含某个元素:

定义一个节点类型的变量,遍历链表的同时并判断,如果cur.val==key时,返回true即可.


public boolean contains(int key) {
        ListNode2 cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

4)找到要删除或插入的元素:

该方法非常重要,插入或删除元素都需要调用它.基于双向链表的特性,我们不论是插入还是删除直接找到当前位置即可,不必像单项链表一样,找到前一个元素的位置.


public ListNode2 searchIndex(int index) {
        if (index<0||index>size()){
            System.out.println("输入位置不合法!");
            return null;
        }
        ListNode2 cur = head;
        while (index!=0){
           cur = cur.next;
           index--;
        }
        return cur;
    }

以上方法均为辅助功能,接下才是双向链表的真正功能.

1)头插法:

基于双向链表的特性,当链表为空时,头结点和尾结点都需要置空.当向head之前插入时需改变node.next的指向和head.prev的指向,并将head向前移动.


public void addFirst(int data) {
        ListNode2 node2 = new ListNode2(data);
        if (head == null) {
            head = node2;
            last = node2;
        } else {
            head.prev = node2;
            node2.next = head;
            head = node2;
        }
    }

2)尾插法:

尾插与头插类似这里不过多赘述,之所以没有将node.next置空是因为,node没有初始化时前驱和后继都为null.


public void addLast(int data) {
        ListNode2 node2 = new ListNode2(data);
        if (head == null) {
            head = node2;
            last = node2;
        } else {
            last.next = node2;
            node2.prev = last;
            last = node2;
        }
    }

3)任意位置插:

head==0时调用头插法,head==size()时调用尾插法.不属于以上两种情况时调用查找函数,接收到指定位置的元素cur.在将node与cur相互绑定即可.


public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("输入位置不合法");
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode2 cur = searchIndex(index);
        ListNode2 node2 = new ListNode2(data);
        node2.next = cur;
        cur.prev.next = node2;
        node2.prev = cur.prev;
        cur.prev = node2;
    }

4)删除第一次出现的元素(key):

这道题代码看似很长其实只要搞清每个if-else之间的关系,就能很容易的写出.首先我们需要用变量cur遍历链表,第一个if-else判断cur是不是要删除的元素,如果是暂定,如果不是cur向后移.当第一个if为真时,第二个if再判断你删除的是否为头结点,如果是头结点并且头结点的下一位不为空,我们让头结点向后移即可,但如果头结点的下一位为空,我们得把last也置为空因为last是成员变量.当第二个if为假时,说明删除的不是头结点,为中间节点.但此时还要注意判断我们删除的元素是不是尾结点,如果是尾结点只需让last向后移即可.


 public void remove(int key) {
        ListNode2 cur = head;//局部变量
        if (head == null) {
            System.out.println("链表为空");
            return;
        }
        while (cur != null) {
            if (cur.val == key) {
                if (head==cur) {
                    head = head.next;
                    if (head!=null){
                        head.prev = null;
                    }else {
                        last = null;
                    }
 
                } else {
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = last.prev;
                    }
                }
                return;
            } else {
                cur = cur.next;
            }
        }
        System.out.println("没有你要删除的元素");
        return;
    }

5)删除所有出现过的元素(key):

与删除一个元素方法基本一致,当删除一个元素不必跳出循环,继续删除即可.


public void removeAllKey(int key) {
        ListNode2 cur = head;//局部变量
        if (head == null) {
            System.out.println("链表为空");
            return;
        }
        while (cur != null) {
            if (cur.val == key) {
                if (cur==head) {
                    head = head.next;
                    if (head!=null){
                        head.prev = null;
                    }else {
                        last = null;
                    }
 
                } else {
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = last.prev;
                    }
                }
            }
                cur = cur.next;
        }
        return;
    }

6)清空链表:

由于head在置空过程中会迷失方向,所以定义curNext来记录head.next帮助head遍历链表.


public void clear() {
        if (head==null){
            return;
        }
        while (head!=null){
            ListNode2 curNext = head.next;
            head.next = null;
            head.prev = null;
            head = curNext;
        }
        last = null;
        System.out.println("置空完毕");
        return;
    }

总结

顺序表与链表的入门以及进阶内容,今天就更新完了,如果我的文章对你的学习有一点点帮助和启发记得三连哦!祝三连的帅哥美女好运连连!

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/661766

[Java]手撕链表面试题及双向链表(进阶)_java 双向链表 面试问题

前言