2023-09-22  阅读(175)
原文作者:李林超 原文地址: https://www.lilinchao.com/archives/483.html

前言

本篇将讲述之前新浪、百度、腾讯的单链表的面试题

单链表面试题

(1)求单链表中有效节点的个数

代码

    //方法:获取到单链表的节点的个数(如果是带头节点的链表,需求不统计头节点)
    public static int getLength(HeroNode head){
        if(head.next == null){//空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助的变量,这里我们没有统计头节点
        HeroNode cur = head.next;
        while(cur != null){
            length++;
            cur = cur.next;//遍历
        }
        return length;
    }

需在SingleLinkedList.class类中添加返回头节点方法:

    //返回头节点
    public HeroNode getHead(){
        return head;
    }

(2)查找单链表中的倒数第k个节点【新浪面试题】

思路: > > 1. 1.编写一个方法,接收head节点,同时接收一个index > > 2. 2.index表示是倒数第index个节点 > 3. 3.先把链表从头到尾遍历,得到链表的总的长度getLength > 4. 4.得到size后,我们从链表的第一个开始遍历(size-index)个,就可以得到 > 5. 5.如果找到了,则返回该节点,否则返回Null

代码

    public static HeroNode findLastIndexNode(HeroNode head,int index){
        //判断如果链表为空,返回null
        if(head.next == null){
            return null;//没有找到
        }
        //第一个遍历得到链表的长度(节点个数)
        int size = getLength(head);
        //第二次遍历  size-index位置,就是我们倒数的第K个节点
        //先做一个index的校验
        if(index <=0 || index > size){
            return null;
        }
        //定义一个辅助变量, for循环定位到倒数的index
        HeroNode cur = head.next;
        for(int i=0;i<size-index;i++){
            cur = cur.next;
        }
        return cur;
    }

(3)单链表的反转【腾讯面试题,有点难度】

图解

202309222128461581.png

202309222128468722.png

思路: > > 1. 1.先定义一个节点reverseHead = new HeroNode(); > 2. 2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead的最前端。 > 3. 3.原来的链表的head.next=reverseHead.next

代码实现

    //将单链表反转
    public static void reversetList(HeroNode head){
        //如果当前链表为空,或者只有一个节点,无需反转,直接返回
        if(head.next == null || head.next.next == null){
            return;
        }
    
        //定义一个辅助的指针(变量),帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点【cur】的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead的最前端
        while(cur != null){
            next = cur.next;//先暂时保存当前节点的下一个节点,因为后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;//将cur连接到新的链表上
            cur = next;//让cur后移
        }
        //将head.next指向reverseHead.next,实现单链表的反转
        head.next = reverseHead.next;
    }

(4)从尾到头打印单链表【百度】

方式1:反向遍历

方式2:Stack栈

图像分析

202309222128475323.png

思路 > > 1. 1.上面的题的要求就是逆序打印单链表 > 2. 2.方式1:先将单链表进行反转操作,然后再遍历即可,这样的做的问题是会破坏原来的单链表的结构,不建议; > 3. 3.方式2:可以利用栈这个数据结构,将各个节点压入到栈中,然后利用栈的先进后出的特点,就实现了逆序打印的效果。

代码实现

测试Stack的使用

    //演示Stack的基本使用
    public class TestStack {
        public static void main(String[] args) {
            Stack<String> stack = new Stack();
            //入栈
            stack.add("jack");
            stack.add("tom");
            stack.add("smith");
    
            //出栈
            while(stack.size()>0){
                System.out.println(stack.pop());//pop就是将栈顶的数据取出
            }
        }
    }

输出结果

    smith
    tom
    jack

代码

    //方式2:可以利用栈这个数据结构,将各个节点压入到栈中,然后利用栈的先进后出的特点,就实现了逆序打印的效果.
    public static void reversePrint(HeroNode head){
        if(head.next == null){
            return;//空链表,不能打印
        }
        //创建一个栈,将各个节点压入栈
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        //将链表的所有节点压入栈
        while(cur != null){
            stack.push(cur);
            cur = cur.next;//cur后移,这样可以压入下一个节点
        }
        //将栈中的节点进行打印,pop出栈
        while(stack.size()>0){
            System.out.println(stack.pop());//stack的特点是先进先出
        }
    }

(5)合并两个有序的单链表,合并之后的链表依然有序

未完成

阅读全文
  • 点赞