【数据结构】单链表面试题（Java + 力扣 + 详解）

🎇🎉🎉🎉点进来你就是我的人了
博主主页：🙈🙈🙈戳一戳，欢迎大佬指点！
人生格言: 当你的才华撑不起你的野心的时候,你就应该静下心来学习!
欢迎志同道合的朋友一起加油喔 💪💪💪
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个🐒嘿嘿
谢谢你这么帅气美丽还给我点赞！比个心

一、移除链表元素

203.移除链表元素

1. 题目

2. 解析

• 特殊情况处理：
• 如果链表头节点 head 为空，直接返回 null，表示链表为空，无需处理。

if(head == null){return null;
}

• 一般情况处理：
• 定义两个指针，prevNode 指向当前节点的前一个节点（初始为头节点），cur 指向当前节点的下一个节点。

ListNode prevNode = head;
ListNode cur = head.next;

• 循环遍历链表：
• 使用 cur 指针遍历链表，当 cur 不为 null 时执行循环。
• 如果 cur 指向的节点的值等于 val，则将 prevNode.next 指向 cur.next，即跳过当前节点 cur。
• 否则，更新 prevNode 为 cur，并将 cur 移动到下一个节点。

while(cur != null){if(cur.val == val){prevNode.next = cur.next;cur = cur.next;}else{prevNode = cur;cur = cur.next;}
}

• 处理头节点：
• 最后处理头节点，如果头节点的值等于 val，则将头节点 head 指向下一个节点，即跳过头节点。

if(head.val == val){head = head.next;
}

• 返回链表头：
• return head; 返回处理后的链表头节点。

3. 完整代码展示

/*** 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) {//特殊情况、链表为空if(head == null){return null;}//处理一般情况//定义两个指针，prev 指向第一个节点，cur 指向第二个节点ListNode prevNode = head;ListNode cur = head.next;//循环判断条件 cur != null//先不考虑 头节点//从第二个节点开始排查while(cur != null){if(cur.val == val){prevNode.next = cur.next;cur = cur.next;}else{prevNode = cur;cur = cur.next;}}//最后处理头节点if(head.val == val){head = head.next;}return head;}
}

二、反转链表

206.反转链表

1. 题目

2. 解析

• 要求：遍历链表一遍就反转完
• 思路：
• 先把原链表的头节点的next置为空，记录好下一个节点，进行头插

• reverseList 方法用于反转单链表，接收一个头节点 head 作为参数，并返回反转后的新头节点。

• 首先进行了几个边界条件的判断：

   如果 head 为 null，即空链表，直接返回 null。如果链表只有一个节点 (head.next == null)，则直接返回 head，因为反转后还是自身。
  

• 若链表节点数大于1，进入反转过程：

  ListNode cur = head.next; 初始化 cur 为 head 的下一个节点。
  head.next = null; 将 head 的 next 指针置为 null，表示反转后的尾节点。
  

• 使用头插法反转链表：

  while (cur != null) 循环直到 cur 为 null：
  ListNode curNext = cur.next; 记录当前节点 cur 的下一个节点。
  

  cur.next = head; 将 cur 的 next 指向 head，完成头插操作。
  head = cur; 更新 head 为当前 cur，即新的头节点。
  cur = curNext; 将 cur 移动到下一个节点，继续反转操作。

• 最终返回 head，此时 head 已经是反转后链表的新头节点。

• 这种方法的时间复杂度为 O(n)，其中 n 是链表的节点数，因为需要遍历整个链表一次来完成反转操作。

3. 完整代码展示

/*** 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;}ListNode cur = head.next;head.next = null;// 进行头插// 进行头插之前要记录好下一个节点while (cur != null) {ListNode curNext = cur.next;cur.next = head;head = cur;cur = curNext;}return head;}
}

三、链表的中间结点

876.链表的中间结点

1. 题目

2. 解析

• 第一种解法：长度 / 2

但是这种 需要遍历一遍链表，还要再除以2，可以在这个基础上进行优化

• 第二种解法：

定义两个指针：（快慢指针）fast快指针 slow慢指针

算法采用了快慢指针技巧：

• fast 指针每次移动两步：fast = fast.next.next;
• slow 指针每次移动一步：slow = slow.next;

由于 fast 指针移动速度是 slow 指针的两倍，所以当 fast 指针到达链表末尾时，slow 指针恰好指向链表的中间节点。

具体执行过程如下：

• 初始时，fast 和 slow 都指向链表的头节点 head。

• 在每一轮循环中，首先检查 fast 是否为空且 fast.next 是否为空（即 fast 是否到达链表尾部）：

  如果是，则退出循环，此时 slow 指向链表的中间节点。
  如果不是，则将 fast 向前移动两步，将 slow 向前移动一步。
  

• 循环结束后，返回 slow，即为链表的中间节点。

• 这段代码的时间复杂度为 O(n)，其中 n 是链表的长度，因为 fast 指针最多遍历链表一次。空间复杂度为 O(1)，因为只使用了常量级的额外空间用于两个指针。

3. 完整代码展示

/*** 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 fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}
}

四、 链表中倒数第k个节点

链表中倒数第k个节点

1. 题目

2. 解析

• 定义了一个简单的链表节点类 ListNode，每个节点包含一个整数值 val 和一个指向下一个节点的引用 next。

• indKthToTail(ListNode head, int k) 方法接收一个链表头节点 head 和一个整数 k，表示要查找倒数第k个节点。
• 首先，使用两个指针 fast 和 slow，初始化都指向头节点 head。
• fast 先移动 k 步，如果 k 大于链表长度，则直接返回 null。
• 然后，fast 和 slow 同时向前移动，直到 fast 到达链表末尾，此时 slow 指向的即为倒数第 k 个节点。
• 返回 slow。

• 在 main 方法中，创建了一个包含五个节点的链表。
• 分别测试了找倒数第1个、第3个节点以及超过链表长度的情况。

3. 完整代码展示

// 定义链表节点类
class ListNode {int val;ListNode next;ListNode(int x) {val = x;}
}public class Solution {public ListNode FindKthToTail(ListNode head, int k) {if (head == null || k <= 0) {return null;}ListNode fast = head;ListNode slow = head;// 快指针先向前移动k步for (int i = 0; i < k; i++) {if (fast != null) {fast = fast.next;} else {// 如果k超过了链表长度，直接返回nullreturn null;}}// 快慢指针一起向前移动，直到快指针到达链表末尾while (fast != null) {fast = fast.next;slow = slow.next;}// 此时slow指向的就是倒数第k个节点return slow;}// 测试代码public static void main(String[] args) {Solution solution = new Solution();// 创建链表：1 -> 2 -> 3 -> 4 -> 5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);// 测试找倒数第1个节点ListNode result = solution.FindKthToTail(head, 1);if (result != null) {System.out.println(result.val); // 输出5} else {System.out.println("找不到节点");}// 测试找倒数第3个节点result = solution.FindKthToTail(head, 3);if (result != null) {System.out.println(result.val); // 输出3} else {System.out.println("找不到节点");}// 测试k超过链表长度result = solution.FindKthToTail(head, 6);if (result != null) {System.out.println(result.val);} else {System.out.println("找不到节点"); // 输出找不到节点}}
}

五、合并两个有序链表

21.合并两个有序链表

1. 题目

2. 解析

• 虚拟节点的创建：

ListNode newNode = new ListNode(1);

这里创建了一个值为 1 的虚拟节点 newNode。这个虚拟节点的作用是作为合并后链表的头节点的前一个节点，简化了链表操作。

• 临时节点：

ListNode tmp = newNode;

tmp 节点用来迭代构建合并后的链表，最初指向 newNode，随着节点的合并不断移动。

• 合并过程：

使用 while 循环，只要 list1 和 list2 都不为 null，比较它们当前节点的值：
如果 list1.val < list2.val，将 tmp.next 指向 list1，然后 list1 向后移动一位，tmp 也向后移动一位。
否则，将 tmp.next 指向 list2，然后 list2 向后移动一位，tmp 也向后移动一位。

• 处理剩余节点：

循环结束后，可能会有一个链表还有剩余节点未合并，使用两个 if 条件分别处理：
如果 list1 不为 null，将剩余的 list1 接在 tmp.next 后面。
如果 list2 不为 null，将剩余的 list2 接在 tmp.next 后面。
返回合并后链表的头节点：返回 newNode.next，即虚拟节点 newNode 的下一个节点，即合并后的链表的头节点。

• 总结

这段代码通过使用虚拟节点和临时节点，在一次遍历中将两个有序链表 list1 和 list2 合并为一个有序链表，并返回合并后链表的头节点。

3. 完整代码展示

/*** 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 list1, ListNode list2) {//创建一个虚拟节点ListNode newNode = new ListNode(1);//临时节点ListNode tmp = newNode;while(list1 != null && list2 != null){if(list1.val < list2.val){tmp.next = list1;list1 = list1.next;tmp = tmp.next;}else{tmp.next = list2;list2 = list2.next;tmp = tmp.next;}}if(list1 == null){tmp.next = list2;}if(list2 == null){tmp.next = list1;}return newNode.next;}
}