devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】链表面试题总结(持续更新中...)_给定一个开始节点,一个结束节点,以及一个链路链表,判断给定的链路是否可以从开始

作者：小小林熬夜学编程 | 2024-05-27 00:10:42

赞

踩

给定一个开始节点,一个结束节点,以及一个链路链表,判断给定的链路是否可以从开始

目录

问题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. }

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号