首页 > 其他分享 >链表面试题解析

链表面试题解析

时间：2023-12-17 19:48:05浏览次数：30  
标签：head null ListNode 试题 val next 表面 解析 cur

链表面试题解析

1. 删除链表中=val的所有节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode cur = head;
        ListNode prev = cur;
        while (cur != null) {
            if (cur.val == val) {
                // 处理头删
                if (cur == head) {
                    head = head.next;
                }else {
                    prev.next = cur.next;
                }
                cur = cur.next;

            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        return head;
    }
}

 

2. 反转一个单链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 处理链表为空
        if (head == null) {
            return null;
        }
        // 处理链表一个节点
        if (head.next == null) {
            return head;
        }
        // 节点 >=2 正常情况反转链表
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head;
            head = cur;
            cur = next;
        }
        return head;
    }
}

 

3. 判断链表的中间结点

思路:

慢指针每次走一步 快指针每次走两步，当快指针走完  慢指针所在位置就是链表的中心节点

注意：判断条件一定得这样写 （fast != null && fast.next != null) ，因为如果是偶数个节点 fast走到最后是null， fast.next写在前面会访问空指针异常

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

 

4. 返回倒数第 k 个节点

思路: 

 

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if (head == null) {
            return null;
        }
        if (k < 0) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = fast;
        
        // 让fast先走k-1步
        int count = 0;
        while (count != k-1) {
            // 当fast.next == null, fast还没有走完k-1步
            // 说明k超过节点大小 不能拿到倒数第k个节点，返回null
            if (fast.next != null) {
                fast = fast.next;
                count++;
            }else {
                return null;
            }
        }
        // 然后同时走
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

5. 合并两个有序链表

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newHead = new ListNode(-1);
        ListNode tail = newHead;
        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tail.next = headA;
                headA = headA.next;
                tail = tail.next;
            }else {
                tail.next = headB;
                headB = headB.next;
                tail = tail.next;
            }
        }
        if (headA != null) {
            tail.next = headA;
        }
        if (headB != null) {
            tail.next = headB;
        }
        return newHead.next;

    }
}

6. 分割链表

使用虚拟节点:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode cur = head;
        ListNode overX = new ListNode(-1);
        ListNode lessX = new ListNode(-1);
        ListNode tailOv = overX;
        ListNode tailLe = lessX; 

        while (cur != null) {
            if (cur.val < x) {
                tailLe.next = cur;
                cur = cur.next;
                tailLe = tailLe.next;
            }else {
                tailOv.next = cur;
                cur = cur.next;
                tailOv = tailOv.next;
            }
        }
        tailOv.next = null;
        tailLe.next = overX.next;
        return lessX.next;
    }
}

不使用虚拟节点:

解决思路与上面一样 只是多了些判断

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // 处理空链表
        if (head == null) {
            return null;
        }
        ListNode headOx = null;
        ListNode headLx = null;
        ListNode tailOx = null;
        ListNode tailLx = null; 
        ListNode cur = head;

        while (cur != null) {
            if (cur.val < x){
                // < x
                if (headLx == null) {
                    headLx = cur;
                    tailLx = headLx;
                }else {
                    tailLx.next = cur;
                    tailLx = tailLx.next;
                }
                cur = cur.next;
            }else {
                // >= x
                if (headOx == null) {
                    headOx = cur;
                    tailOx = headOx;
                }else {
                    tailOx.next = cur;
                    tailOx = tailOx.next;
                }
                cur = cur.next;
            }
        }
        // 分割链表后可能 headLx为空 或者 headOx为空，但是不可能都为空
        if (headLx == null) {
            return headOx;
         }
        // 走到这里表示< x 的链表不为空，直接链接headOx
        // 可以直接链接是因为 无论 val > x 链表是否有节点都对结果不影响
        // 为空: headOx = null, tailLx.next = headOx(null)
        tailLx.next = headOx;
        // 但是最后需要判断 因为最后一个节点得置空 
        if (tailOx != null)         
            tailOx.next = null;    
        return headLx;
    }
}

7. 回文链表

方法1: 思路

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, L istNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 1. 找到中间节点
        ListNode fast = head;
        ListNode slow = fast;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2. 从中间节点开始反转链表
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = slow;
            slow = cur;
            cur = next;
        }
        // 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;
    }
}

方法2:

解题的思路与方法1一样 只是在反转链表时将中间节点置空 然后判断回文

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode findMiddleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = fast;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverseList(ListNode head) {
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head;
            head = cur;
            cur = next;
        }
        return head;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode midNode = findMiddleNode(head);
        ListNode newHead = reverseList(midNode);
        // 判断链表是否回文       
        while (head.next != null) {
            if (head.val != newHead.val) {
                return false;
            }else {
                head = head.next;
                newHead = newHead.next;
            }
        }
        return true;
    }
}

8. 相交链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 1. 计算两个链表长度
        ListNode curL = headA; // curL指向长链表
        ListNode curS = headB; // curS指向短链表
        int lenL = 0;
        int lenS = 0;
        while (curL != null) {
            lenL++;
            curL = curL.next;
        }
        while (curS != null) {
            lenS++;
            curS = curS.next;
        }
        curL = headA;
        curS = headB;   
        // 2. 让curL先走差距步
        int gap = lenL - lenS;
        if (gap < 0) {
            curL = headB;
            curS = headA;
            gap = lenS - lenL;
        }
        while (gap != 0) {
            curL = curL.next;
            gap--;
        }
        // 3. 同时走 判断链表是否相交
        // 判断方法1:
        // while (curL != null && curS != null) {
        //     if (curL == curS) {
        //         return curL;
        //     }
        //     curL = curL.next;
        //     curS = curS.next;
        // }
        // return null;
        
        // 判断方法2:
        while (curL != null && curS != null && curL != curS) {
            curL = curL.next;
            curS = curS.next;
        }
        if (curL == curS && curL == null) return null;
        
        return curL;
    
    }
}

9. 环形链表

解题思路:

slow慢指针一次走一步 fast快指针一次走两步, 如果快指针与慢指针在圈内相遇 该链表就是环形链表

问题:

1. 为什么可以用快慢指针思路解这道题 ?

slow 一次走一步 fast一次走两步，在圈内会不会错过 不会相遇 ?

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = slow;
        // 有可能链表不是环形 
        while (fast != null && fast.next != null) {
           slow = slow.next;
           fast = fast.next.next;
           if (slow == fast) {
               return true;
           } 
        }
        return false; 
    }
}

10. 找环形链表入口点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        
        // 1. 找到相遇点
        ListNode slow = head;
        ListNode fast = slow;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 走到这里 有两种情况:
        // 1. fast走到null(偶数节点) 或者 fast.next = null(奇数节点) ——》 无环 
        // 2. fast与slow相遇后break
        if (fast == null || fast.next == null) return null;

        // 2. 找到入环点
        ListNode cur = head;
        while (cur != slow) {
            cur = cur.next;
            slow = slow.next;
        }
        return cur;
    }
}

 

标签：head,null,ListNode,试题,val,next,表面,解析,cur
From： https://www.cnblogs.com/xumu7/p/17903168.html

相关文章

  • 05.capability 配置参数解析
    capability配置参数解析Capability简介功能：配置Appium会话，告诉Appium服务器需要自动化的平台的应用程序形式：键值对的集合，键对应设置的名称，值对应设置的值主要分为三部分公共部分ios部分android部分SessionAppium的客户端和服务端之间进行......
  • 深度解析Python上下文管理器：优雅资源管理与异常处理
    Python是一种功能强大且灵活的编程语言，它提供了许多高级工具和特性来简化开发过程。其中之一就是上下文管理器，它允许开发者更优雅地处理资源管理和异常处理。本文将深入探讨Python中上下文管理器的工作原理、使用方法以及实际应用。1. 什么是上下文管理器？上下文管理器是一种Python......
  • 2023最新中级难度CSS面试题,包含答案。刷题必备！记录一下。
    好记性不如烂笔头内容来自面试宝典-中级难度CSS面试题合集问:描述一下CSS的作用和重要性。CSS（CascadingStyleSheets）是一种用于定义网页元素外观和表现的样式表语言，它对于网页设计至关重要。CSS的主要作用有以下几点：样式控制：通过CSS，开发者可以为网页上的文本、图像和其......
  • 2022年RHCE认证考题解析最新版—RH294环境【转】
    由于本人10.17已成功考过CSA，经过两周所学的ansible并结合题库整理出来的CE解析版我也是11月月底就要考了，不过这套解析也是可以满足今年的redhat8题库文中可能涉及一些命令的参数解释，如有不懂的伙伴可参考我的笔记Ansibleps：一切模板似的题库考试，都需要经过大脑的理解方可顺利上......
  • Java之可变参数和Collections的详细解析
     1.可变参数在JDK1.5之后，如果我们定义一个方法需要接受多个参数，并且多个参数类型一致，我们可以对其简化.格式：修饰符返回值类型方法名(参数类型...形参名){}底层：其实就是一个数组好处：在传递数据的时候，省的我们自己创建数组并添加元素了，JDK底层帮我们自动创建数组并添加元素了......
  • 代码随想录算法训练营第四天 | 24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，
    一、24.两两交换链表中的节点题目链接：LeetCode24.两两交换链表中的节点学习前：思路：未新增虚拟结点。节点数为0,1,2需要另外讨论。当节点数>=2时，返回的head值为第2个节点，需要3个指针first、second、prev，分别是第一个节点和第二个节点，以及第一个节点的前节点。while(first......
  • 一道很不错的高中数学题的题解解析
    引：上周六上午把一道高中的数学竞赛题（一道8分的填空题，原题如下图所示）当成一道大题（如上）郑重其事地和孩子以互动的方式探讨了这个题的题解分析. 这是一道出得很好的题.其题解所涉及的知识不超出高一目前所学内容，因此高一的学生也是可能做得出来的.但这题是一道很综合的题，涉......
  • Feign源码解析：初始化过程（一）
    前言打算系统分析下Feign的代码，上一篇讲了下Feign的历史，本篇的话，先讲下Feign相关的beanDefinition，beanDefinition就是bean的设计图，bean都是按照beanDefinition来制造的。Feign相关的bean不少，有一些是因为我们的Feign相关注解而引入的，有一部分是因为spring的自动装配来自动引入的......
  • 【LevelDB】【include】Slice类解析
    Slice类Slice类是对字符串的封装，设计思想与std::string_view相似。源文件位置include/leveldb/slice.h优点：1、拷贝速度快，Slice的拷贝仅需拷贝数据指针和数据长度2、多个Slice可指向同个字符串，减少资源开销3、支持std::string......
  • 面试题 02.07. 链表相交
    题目面试题02.07.链表相交要求给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。思路和答案这道题目先用暴力破解，直接使用双层for循环，如下：/***暴力破解，双层for循环**@paramheadA*@param......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99