首页 > 其他分享 >单链表经典面试题

单链表经典面试题

时间:2023-03-10 18:13:46浏览次数:40  
标签:Node 面试题 单链 head next 链表 经典 curNode 节点

单链表经典面试题

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

思路:直接遍历节点个数即可,如果带头节点则不统计头节点

方法代码:

/**
 * 遍历求链表有效节点个数,但不统计头节点
 * @param head 传入头节点
 * @return 返回有效节点个数
 */
public int getLength(Node head) {
    // 判断是否为空
    if (head.next == null) {
        return 0;
    }
    Node temp = head;
    int length = 0;
    while (temp.next != null) {
        length++;
        temp = temp.next;
    }
    return length;
}

2. 查找单链表中的倒数第k个节点

思路:要求只能遍历一次链表,利用双指针

  • 定义front和rear两个快慢指针,初始时都指向headNode;
  • 求倒数第k个节点,front快指针先走k步;
  • 之后front和rear同时向后遍历,当front走到链表尾部时停止,此时rear所指的节点即为要找的倒数第k个节点。
/**
 * 利用双指针,仅遍历一次找到链表的倒数第k个节点
 * @param head 传入头节点
 * @param index 传入的k值
 * @return 返回找到的倒数第k个节点
 */
public Node findLastIndexNode(Node head, int index) {
    if (head.next == null) { // 判断链表是否为空
        return null;
    }
    // 校验index,index值应为正值且不能大于链表长度
    int size = getLength(head);
    if (index <= 0 || index > size) return null;
    // 定义快慢两个指针
    Node front = head;
    Node rear = head;
    // 快指针先走index步
    for (int i = 0; i < index; i++) {
        front = front.next;
    }
    // 遍历至链表尾部
    while (front != null) {
        front = front.next;
        rear = rear.next;
    }
    return rear;
}

3. 单链表的反转

两种思路:

  • 单链表的"头插法"
    • 先定义一个新节点reverseHead当作新链表的头节点;
    • 遍历原来的链表,并定义curNode和nextNode用于记录当前遍历的节点及其下一个节点,保证链表不断开;
    • 每遍历一个curNode,就将其从原链表取出,放入新链表的头节点reverseHead之后
    • 令head.next = reverseHead.next,也即让原链表的头节点的next域指向新链表reverseHead的下一个节点,即反转后的链表替换掉了已经为空的原链表。
/**
 * 利用单链表的“头插法”的思想反转链表
 * @param head 传入原链表的头节点
 */
public void reverseList(Node head) {
    // 判断链表是否为空 || 链表只有一个有效节点,则不需要反转,直接return
    if (head.next == null || head.next.next == null) return;
    // 定义一个新的节点作为新链表的头节点
    Node reverseHead = new Node(0);
    // 定义两个辅助变量,cur指向原链表遍历时的当前节点,next用于记录cur的下一个节点
    Node curNode = head.next;
    Node nextNode = null;
    while (curNode != null) {
        // 每次遍历前先记录nextNode,防止cur取出后原链表断开丢失位置
        nextNode = curNode.next;
        // 将curNode与新链表建立连接
        curNode.next = reverseHead.next;
        reverseHead.next = curNode;
        // 后移
        curNode = nextNode;
    }
    // 将新链表接入原链表完成反转
    head.next = reverseHead.next;
}
  • 原地反转
    • 原地反转与“头插法”的思路类似,但区别在于,原地反转直接对原链表修改,不建立新的链表
    • 同样需要定义两个辅助变量preNode和curNode分别用于记录当前遍历的节点及其前一个节点;
    • 初始状态下,preNode = head.next,curNode = preNode.next;
    • 将curNode从原链表中取出,即preNode.next指向原来curNode的下一个节点,并将其转而添加到头节点之后(即链表头处);
    • 由于原本的curNode已完成反转,继续向后遍历时preNode不动,新的curNode = preNode.next。
/**
 * 就地反转链表,与“头插法”思想类似,将curNode插入到head头节点之后,但不创建新链表
 * @param head 传入头节点
 */
public void localReverseList(Node head) {
    // 判断链表是否为空 || 链表只有一个有效节点,则不需要反转,直接return
    if (head.next == null || head.next.next == null) return;
    Node preNode = head.next;
    Node curNode = preNode.next;
    while (curNode != null) {
        // 取出curNode,让preNode与后续节点建立联系
        preNode.next = curNode.next;
        // 将curNode插入到链表头,即head节点之后
        curNode.next = head.next;
        head.next = curNode;
        // 新的curNode后移
        curNode = preNode.next;
    }
}

4. 从尾到头打印单链表

两种思路:

  • 方式一:先将单链表反转,然后再遍历。但题目要求仅要求逆序打印,反转会破坏原来单链表的结构,这样实现后若要求再次顺序打印就会有问题。
  • 方式二:利用栈这个数据结构。将各个节点压入栈中,然后利用栈的先入后出的特点来实现逆序打印
/**
 * 利用栈逆序打印单链表,不破坏原来的链表结构
 * @param head 传入头节点
 */
public void reversePrint (Node head) {
    // 判空
    if (head.next == null) return;
    Node temp = head.next;
    // 创建一个栈
    Stack<Node> stack = new Stack<>();
    // 遍历链表,将节点压入栈中
    while (temp != null) {
        stack.push(temp);
        temp = temp.next;
    }
    // 将节点依次从栈顶弹出
    while (!stack.isEmpty()) {
        System.out.println(stack.pop());
    }
}

5. 合并两个有序的单链表,使得合并之后的链表依然有序

/**
 * 合并两个有序链表
 * @param head1 传入第一个链表的头节点
 * @param head2 传入第二个链表的头节点
 * @return 返回合并后的新链表的头节点
 */
public Node mergeTwoLists(Node head1, Node head2) {
    // 先判断边界值,两链表为空的情况
    if (head1.next == null) return head2;
    if (head2.next == null) return head1;
    // 创建一个新的头节点,以及一个辅助变量temp
    Node newHead = new Node(0);
    Node temp = newHead;
    // 当两个链表都仍在遍历有效值时
    while (head1.next != null && head2.next != null) {
        // 判断分别在两链表当前位置的节点value,哪个更小temp就指向谁
        if (head1.next.value < head2.next.value) {
            temp.next = head1.next;
            // 不断移动temp以及两链表遍历的当前节点
            temp = temp.next;
            head1.next = head1.next.next;
        }else {
            temp.next = head2.next;
            temp = temp.next;
            head2.next = head2.next.next;
        }
    }
    // 当有一个链表遍历到空值时退出循环,
    // 此时将另一个还未遍历完全的链表的剩余节点直接接入到temp后,即拼接到新链表之后
    if (head1.next == null) {
        temp.next = head2.next;
    }
    if (head2.next == null) {
        temp.next = head1.next;
    }
    return newHead;
}

标签:Node,面试题,单链,head,next,链表,经典,curNode,节点
From: https://www.cnblogs.com/SnkrGao/p/17204329.html

相关文章

  • 小程序面试题
    小程序有哪些常用的生命周期onLoad—-监听页面加载onReady—-监听页面初次渲染完成onShow—-监听页面显示onHide—-监听页面隐藏onUnload—-监听页面卸载小程序有那几个......
  • 前端面试题(html+css)
    HTML1、h5新增标签header、footer、 nav、article、aside、audio、video……等2、html语义化HTML语义化就是指在使用HTML标签构建页面时,要求尽可能的使用具有语义的......
  • 面试题小整理
    问题1:什么是幂等性?幂等性其实就是保证这个接口的执行结果只影响一次,后续即便再次调用,也不能对数据产生影响。幂等测试就是验证数据一致性和事务完整性。可能出现幂等......
  • #yyds干货盘点# LeetCode面试题:字符串相乘
    1.简述:给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。注意:不能使用任何内置的BigInteger库或直接将输......
  • 【数据结构入门】单链表(SList)详解(增、删、查、改)
    1、链表的概念及结构1.1链表的概念概念:链表是一种物理存储结构上非连续、非顺序的存储结构,但链表在逻辑上是连续的,顺序的,而数据元素的逻辑顺序是通过链表中的指针连接次序实......
  • 软件测试常见面试题1000问涵盖一千+公司面试软件测试面试题(全网最全)
    前前后后面试了有20多家的公司吧,最近抽空把当时的录音整理了下,然后给大家分享下开头都是差不多,就让做一个自我介绍,这个不用再给大家普及了吧视频教程:【【呕心沥血】耗时7天......
  • 数据类型扩展及面试题讲解
    packageJavanote;importjava.math.BigDecimal;publicclassDemo01{publicstaticvoidmain(String[]args){//整数拓展:进程二进制0b......
  • #yyds干货盘点# LeetCode面试题:接雨水
    1.简述:给定 n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例1:输入:height=[0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数......
  • Python常见面试题010. Python的整形占多大内存?
    010.Python的整形占多大内存?示例代码importsysa=0print(a.__sizeof__())#24print(sys.getsizeof(a))#24所以答案是24?并不是!看下面importsysb=1pr......
  • Python常见面试题011. 如何在Python中动态创建类?
    011.如何在Python中动态创建类?说在前面答案是type你印象中的type是用来查看对象的类型的li=[]type(li)#得到list对自定义的类是这样的classPerson:......