• 【数据结构】链表面试题总结(持续更新中...)

    目录

    问题1：删除链表中等于给定值 val 的所有节点

    问题2：反转一个单链表

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

    问题4：输入一个链表，输出该链表中倒数第k个结点

    问题5：合并两个有序列表

    问题6：以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

    问题7：请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

    问题8：链表的回文结构

    问题9：输入两个链表，找出它们的第一个公共结点

    问题10：判断链表中是否有环

    问题11：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

    问题1：删除链表中等于给定值 val 的所有节点

    OJ链接：203. 移除链表元素 - 力扣（LeetCode）

    问题描述：

     解题思路：

    要点1：先不管第一个节点，从第二个节点开始。

    要点2：需要保存待删除节点的前驱节点

    要点3：如果满足删除条件，pre.next = cur.next

    要点4：最后判断第一个节点是否需要删除

    实现代码：

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     public ListNode removeElements(ListNode head, int val) {
    13.         if(head == null){
    14.             return null;
    15.         }
    16.         // 先不管第一个节点，从第二个节点开始判断。
    17.         // 需要保存待删除节点的前驱节点
    18.         ListNode pre = head;
    19.         ListNode cur = pre.next;
    20.         while(cur != null){
    21.             if(cur.val == val){
    22.                 // 如果相等，直接删除
    23.                 pre.next = cur.next;
    24.                 cur = cur.next;
    25.             }else{
    26.                 // 一起向后移动
    27.                 pre = cur;
    28.                 cur = cur.next;
    29.             }
    30.         }
    31.         // 判断头节点是否需要删除
    32.         if(head.val == val){
    33.             head = head.next;
    34.         }
    35.         return head;
    36.  
    37.     }
    38. }

    问题2：反转一个单链表

    OJ链接：206. 反转链表 - 力扣（LeetCode）

    问题描述：

      解题思路：

    要点1：采用头插法

    要点2：定义傀儡节点为null，这个节点的初值是反转链表的尾巴。定义为null最合适

    要点3：依次将每个节点插在newHead前面。每插一次，更新newHead的位置

    实现代码：

    1. class Solution {
    2.     public ListNode reverseList(ListNode head) {
    3.         if(head == null){
    4.             return null;
    5.         }
    6.         // 定义一个傀儡节点
    7.         ListNode newHead = null;
    8.         ListNode cur = head;
    9.         // 依次将每个节点使用头插法 插在newHead的前面
    10.         while(cur != null){
    11.             ListNode curNext = cur.next;
    12.             cur.next = newHead;
    13.             newHead = cur;
    14.             cur = curNext;
    15.         }
    16.         return newHead;
    17.     }
    18.         
    19. }

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

    OJ链接：876. 链表的中间结点 - 力扣（LeetCode）

    问题描述：

     解题思路：

    要点1：快慢节点。第一个节点的速度是第二个速度的二倍。

    原因：假设一段路为L，当A的速度是B的速度的两倍，同样的时间，当A跑完全程，B就会跑动中点

    要点2：遍历链表的条件是：fast != null && fast.next != null

    原因：因为fast要连走两步，如果fast.next=null，走第二步就会报空指针异常

    实现代码：

    1. class Solution {
    2.     public ListNode middleNode(ListNode head) {
    3.         if(head == null){
    4.             return null;
    5.         }
    6.         ListNode fast = head;
    7.         ListNode slow = head;
    8.         while(fast != null && fast.next != null){
    9.             fast = fast.next.next;
    10.             slow = slow.next;
    11.         }
    12.         return slow;
    13.     }
    14. }

    问题4：输入一个链表，输出该链表中倒数第k个结点

    OJ链接：链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

    问题描述：

    解题思路：

    要点1：让快的节点先走k-1步。

    要点2：k要是为0，直接返回null

    要点3：k如果大于链表的长度，直接返回null。在fast走K步的过程中，判断fast=null

    要点4：fast先走K步后，fast和slow的速度一样

    要点5：fast走到最后一个节点时，返回slow

    实现代码：

    1. public class Solution {
    2.     public ListNode FindKthToTail(ListNode head,int k) {
    3.         if(head == null){
    4.             return null;
    5.         }
    6.         // 返回倒数第K个，快比慢多走K-1步
    7.         ListNode fast = head;
    8.         ListNode slow = head;
    9.         if(k == 0){
    10.             return null;
    11.         }
    12.         // 先让快的先走
    13.         while(k-1 > 0){
    14.             fast = fast.next;
    15.             if(fast == null){
    16.                 // 证明K大于链表个数
    17.                 return null;
    18.             }
    19.             k--;
    20.         }
    21. // fast走到最后一个节点，就停止，当fast.next =null，就不进入这个while
    22.         while(fast != null && fast.next != null){
    23.             fast = fast.next;
    24.             slow = slow.next;
    25.         }
    26.         return slow;
    27.  
    28.     }
    29. }

    问题5：合并两个有序列表

    OJ链接：21. 合并两个有序链表 - 力扣（LeetCode）

    问题描述：

     解题思路：

    要点1：定义一个傀儡节点，将小的节点往这个傀儡节点后面加

    要点2：两个链表的长度不一定相等，跳出 while(cur1 != null && cur2 != null)，至少有一个链表已经遍历介绍，将还没遍历完的链表的剩余节点加载newCur的后面

    实现代码：

    1. class Solution {
    2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    3.         if(list1 == null){
    4.             return list2;
    5.         }
    6.         if(list2 == null){
    7.             return list1;
    8.         }
    9.         ListNode newHead = new ListNode(-1);
    10.         ListNode cur1 = list1;
    11.         ListNode cur2 = list2;
    12.         // 定义一个傀儡节点，把小的节点往这个傀儡节点后面添加，每次添加后，更新newCur的位置
    13.         ListNode newCur = newHead;
    14.         while(cur1 != null && cur2 != null){
    15.             if(cur1.val >= cur2.val){
    16.                 newCur.next = cur2;
    17.                 cur2 = cur2.next;
    18.                 newCur = newCur.next;
    19.             }else{
    20.                 newCur.next = cur1;
    21.                 cur1 = cur1.next;
    22.                 newCur = newCur.next;
    23.             }
    24.         }
    25.         // 因为两个链表的长度不一定相等，经过上面的while，至少有一个链表已经遍历结束了
    26.         // 将不为空的链表加载newCur的后面
    27.         if(cur1 != null){
    28.             newCur.next = cur1;
    29.         }
    30.         if(cur2 != null){
    31.             newCur.next = cur2;
    32.         }
    33.         return newHead.next;
    34.     }
    35. }

    问题6：以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

    OJ链接：链表分割_牛客题霸_牛客网 (nowcoder.com)

    问题描述：

    解题思路：

    要点1：定义两个链表。第一个链表存放比x小的值，第二个链表存放比x大的值。然后将这两个链表串在一起

    要点2：使用尾插法

    要点3：注意注意，第一个和第二个都有可能为空。当第二段不为空，需要修改链表末尾位置的指向

    要点4：cur.val < x,不能写小于等于。如果加上等于，就会出现比x小的值在x的后面这种情况

    实现代码：

    1. public class Partition {
    2.     public ListNode partition(ListNode pHead, int x) {
    3.         if(pHead == null){
    4.             return null;
    5.         }
    6.         // 用来存放比x小的元素（有可能为空）
    7.         ListNode s1 = null;
    8.         ListNode e1 = null;
    9.         // 用来存放比x大的元素（有可能为空）
    10.         ListNode s2 = null;
    11.         ListNode e2 = null;
    12.         // 需要对新链表的尾节点处理
    13.         ListNode cur = pHead;
    14.         while(cur != null){
    15.             if(cur.val < x){
    16.                 if(s1 == null){
    17.                     // 第一次插入，s1和e1都指向该元素
    18.                     s1 = cur;
    19.                     e1 = cur;
    20.                 }else{
    21.                     e1.next = cur;
    22.                     e1 = e1.next;
    23.                 }
    24.             }else{
    25.                 if(s2 == null){
    26.                     s2 = cur;
    27.                     e2 = cur;
    28.                 }else{
    29.                     e2.next = cur;
    30.                     e2 = e2.next;
    31.                 }
    32.             }
    33.             cur = cur.next;
    34.         }
    35.         if(s1 == null){
    36.             return s2;
    37.         }
    38.         // 拼接两个链表
    39.         e1.next = s2;
    40.         
    41.         if(s2 != null){
    42.             e2.next = null;
    43.         }
    44.         return s1;
    45.         
    46.     }
    47. }

    问题7：请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

    OJ链接：删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)

    问题描述：

     

     解题思路：

    要点1：定义一个傀儡节点。如果相邻元素不相同，就采用尾插法插到傀儡节点的后面。如果相等。就让cur往后移，跳过所有相等的点。让tmp.next = cur;

    实现代码：

    1. public class Solution {
    2.     public ListNode deleteDuplication(ListNode pHead) {
    3.         if(pHead == null || pHead.next == null){
    4.             return pHead;
    5.         }
    6.         ListNode newHead = new ListNode(-1);
    7.         ListNode cur = pHead;
    8. //         ListNode curNext = null;
    9.         ListNode tmp = newHead;
    10.         while(cur != null){
    11.             if(cur.next != null && cur.val == cur.next.val){
    12.                 while(cur.next != null && cur.val == cur.next.val){
    13.                     cur = cur.next;
    14.                 }
    15. // 移到相等的下一个节点
    16.                 cur = cur.next;
    17.             }else{
    18.                 tmp.next = cur;
    19.                 tmp = tmp.next;
    20.                 cur = cur.next;
    21.             }
    22.         }
    23.         tmp.next = null;
    24.         return newHead.next;
    25.  
    26.     }
    27. }

    问题8：链表的回文结构

    OJ链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

    问题描述：

     解题思路：

    要点1：找到中间的节点，中间节点之后的节点挨个反转。

    要点2：如果节点是奇数个，循环结束的条件是head1和head2相遇

    要点3：如果节点是奇数个，循环结束的条件是head1.next = head2

    实现代码：

    1. public class PalindromeList {
    2.     public boolean chkPalindrome(ListNode A) {
    3.         if(A == null){
    4.             return false;
    5.         }
    6.         if(A.next == null){
    7.             return true;
    8.         }
    9.         
    10.         ListNode fast = A;
    11.         ListNode slow = A;
    12.         while(fast != null && fast.next != null){
    13.             fast = fast.next.next;
    14.             slow = slow.next;
    15.         }
    16.         // 此时slow就是中间节点,从slow开始翻转
    17.         ListNode cur = slow.next;
    18.         while(cur != null){
    19.             ListNode curNext = cur.next;
    20.             // 头插法，将cur插在slow前面
    21.             cur.next = slow;
    22.             slow = cur;
    23.             cur = curNext;
    24.         }
    25.         // 从两头开始遍历，判断是否相等
    26.         ListNode head1 = A;
    27.         ListNode head2 = slow;
    28.         // head1.next == head2,证明是偶数个节点，并且相遇，返回true
    29.         while(head1 != head2 && head1.next != head2){
    30.             if(head1.val != head2.val){
    31.                 return false;
    32.             }
    33.             head1 = head1.next;
    34.             head2 = head2.next;
    35.         }
    36.         return true;
    37.     }
    38. }

    问题9：输入两个链表，找出它们的第一个公共结点

    OJ链接：160. 相交链表 - 力扣（LeetCode）

    问题描述：

     解题思路：

    要点1：先求两个链表的长度，长度的差值就是长的链表需要先走的步数。

    起点不一样，终点一样，速度一样，要想相遇，就得让距离远的先走

    要点2：约定：cur1永远指向长的链表的起点，cur2永远指向短的链表的起点，len永远是正数。

    要点3：由于求长度的时候cur1和cur2已经为null，需要重新对这两个赋值

    要点4：这两个链表有可能不相交，如果其中一个cur已经为null了.还没有相等，就证明不相交

    实现代码：

    1. public class Solution {
    2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    3.         if(headA == null){
    4.             return null;
    5.         }
    6.         if(headB == null){
    7.             return null;
    8.         }
    9.         int lenA = 0;
    10.         int lenB = 0;
    11.         ListNode cur1 = headA;
    12.         ListNode cur2 = headB;
    13.         while(cur1 != null){
    14.             cur1 = cur1.next;
    15.             lenA++;
    16.         }
    17.         while(cur2 != null){
    18.             cur2 = cur2.next;
    19.             lenB++;
    20.         }
    21.         int len = lenA - lenB; 
    22.         // 约定cur1指向长的链表  cur2指向短的链表  len永远是正数
    23.         if(len < 0){
    24.             cur1 = headB;
    25.             cur2 = headA;
    26.             len = lenB - lenA;
    27.         }else{
    28.             // 在求长度的时候，cur1和cur2已经走到了两个链表的末尾，需要重新赋值
    29.             cur1 = headA;
    30.             cur2 = headB;
    31.         }
    32.         // 让长的先走
    33.         while(len >0 ){
    34.             cur1 = cur1.next;
    35.             len--;
    36.         }
    37.         while(cur1 != cur2){
    38.             // 如果cur1走到终点，还没有相等，证明不相交
    39.             if(cur1 == null){
    40.                 return null;
    41.             }
    42.             cur1 = cur1.next;
    43.             cur2 = cur2.next;
    44.         }
    45.         return cur1;
    46.     }
    47. }

    问题10：判断链表中是否有环

    OJ链接：141. 环形链表 - 力扣（LeetCode）

    问题描述：

     

     解题思路：

    要点1：快慢指针。fast是slow速度的二部，如果是个圆，则两个一定会相遇。

    实现代码：

    1. public class Solution {
    2.     public boolean hasCycle(ListNode head) {
    3.         if(head == null){
    4.             return false;
    5.         }
    6.         if(head.next == null){
    7.             return false;
    8.         }
    9.         ListNode faster = head;
    10.         ListNode slow = head;
    11.         while(faster != null && faster.next != null && slow != null){
    12.             faster = faster.next.next;
    13.             slow = slow.next;
    14.             if(faster == slow){
    15.                 return true;
    16.             }
    17.         }
    18.         return false;
    19.     }
    20. }

    问题11：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

    OJ链接：142. 环形链表 II - 力扣（LeetCode）

    问题描述：

      解题思路：

    要点1：先使用快慢指针判断是否有环

    要点2：h=L，让slow回到起点，fast不动。因为slow和fast距离入环点的距离一样，以相同的速度移动，相遇点就是入环点

    要点3：如果L为0.当slow走一圈，fast走两圈。会在head相遇。所以如果slow=fast=head，证明head就是入环点。

     

    实现代码：

    1. public class Solution {
    2.     public ListNode detectCycle(ListNode head) {
    3.         if(head == null || head.next == null){
    4.             return null;
    5.         }
    6.         ListNode fast = head;
    7.         ListNode slow = head;
    8.         while(fast != null && fast.next != null && slow != null){
    9.             fast = fast.next.next;
    10.             slow = slow.next;
    11.             if(fast == slow){
    12.                 break;
    13.             }
    14.         }
    15.          // 便秒已经遍历完了，还没有相交，证明链表没有环
    16.         if(fast == null || fast.next == null){
    17.             return null;
    18.         }
    19.         // 在这种情况下，整个链表是一个完整的圈，fast是slow速度的二倍，fast走两圈，slow走一圈，才能相遇，只能在起点相遇
    20.         if(slow == head && fast == head){
    21.             return head;
    22.         }
    23.          slow = head;
    24.          // 
    25.          while(slow != fast){
    26.              slow = slow.next;
    27.              fast = fast.next;
    28.          }
    29.          return slow;
    30.     }
    31. }

  • 相关阅读:
    Docker的网络模式
    Python二级综合题：计算总成绩 五种解法
    C++——酒店管理系统
    strcmp函数详解：字符串比较的利器
    全球化浪潮下的技术与安全
    《Spring Security 简易速速上手小册》第1章 Spring Security 概述（2024 最新版）
    ESP32用作经典蓝牙串口透传模块与手机进行串口通信
    具有Postman + Swagger + Mock + JMeter所有功能的工具
    【opencv-c++】cv::createShapeContextDistanceExtractor形状上下文距离匹配算法
    2022年《一生一系统作业》python练习题
  • 原文地址：https://blog.csdn.net/weixin_44258092/article/details/126197033