单链表常见面试题 —— LeetCode

一.删除链表中与val相等的所有节点

1.题目描述 ----- 203. 移除链表元素 - 力扣（LeetCode）

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

• 列表中的节点数目在范围 [0, 10^4] 
• 1 <= Node.val <= 50
• 0 <= val <= 50

2.思路分析

思路分析: 快慢指针: 定义一个slow指针和一个fast指针;

• fast指针用于遍历链表, 查找链表和val相同的节点
• slow指针用于删除fast查找的和val相同的节点
• fast指向和val相同的节点时, 让slow的下一个指向fast的下一个(不是slow改变了, 是它的下一个指向改变), fast后移; fast指向和val不相等的节点时, 直接让slow指向fast, fast后移

3.算法过程

• 定义快慢指针, 快指针用于遍历链表, 慢指针用于删除和val相同的节点
  slow = head; fast = head.next;
• 遍历链表, 把和val相同的节点都删掉 a.
  • 快指针的val是否和给定的val相同
    slow.next = fast.next; fast = fast.next;
  • 快指针的val和给定的val不相同
    slow = fast; fast = fast.next;
• 判断头节点: 因为我们是从第二个节点开始判断的
  if(head.val == val) head = head.next;

4.代码详解

class Solution {public ListNode removeElements(ListNode head, int val) {// 判空if (head == null) return head;// 定义前驱和后继// 前驱用于指向不是和 val 相等的节点// 后继用于遍历链表ListNode prev = head;ListNode cur = head.next;while (cur != null) {// 节点值和 val 相等if (cur.val == val) {// 让前驱 prev 指向后继 cur 的下一个节点处prev.next = cur.next;} else {// 不相等，让前驱 prev 走一步prev = prev.next;}// 继续判断下一个节点cur = cur.next;}// 头节点和 val 相等的情况if (head.val == val) {head = head.next;}// 返回修改后的链表return head;}
}

二.反转链表

1.题目描述 ----- 206. 反转链表 - 力扣（LeetCode）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

2.思路分析

思路分析: 遍历+头插: 使用cur指针进行边遍历边头插

• 让cur指针指向head的下一个节点, 遍历cur;
• 使用curNext指针指向cur的下一个节点, 即记录cur的下一节点的位置
• 进行头插, 把cur的下一个指向head, 让head又指向cur
• cur重新指向curNext, 即保存了cur的下一个节点的指针

3.算法过程

• head为空, 直接返回head  
  if(head == null) return head;
• 定义cur, cur指向head.next  
  cur = head.next;
• 把head.next置空, 防止形成环
  head.next = null;
• 遍历cur链表
  • 保存cur的下一个节点的位置, 防止找不到无法进行反转
    curNext = cur.next;
  • 进行头插法
    cur.next = head; head = cur;
  • cur指向下一个节点(遍历)
    cur = curNext;
• 返回反转后的链表 return head;

4.代码详解

class Solution {public ListNode reverseList(ListNode head) {// 判空if (head == null) return head;// 获取头节点之后的节点ListNode cur = head.next;// 把头节点之后的节点置空，防止循环链表head.next = null;// 当 cur 为空后，跳出循环while (cur != null) {// 获取 cur 的下一个节点ListNode curNext = cur.next;// 头插cur.next = head;head = cur;// cur 重新指向 cur 的下一个节点cur = curNext;}// 返回翻转后的头节点return head;}
}

三.返回链表的中间节点

1.题目描述 ----- 876. 链表的中间结点 - 力扣（LeetCode）

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

2.思路分析

思路分析: 快慢指针

当快指针的速度是慢指针的2倍时, 快指针走完链表后, 慢指针刚好到链表的中间位置

3.算法过程

• 定义快慢指针
  fast = head; slow = head;
• 遍历链表, 快指针每次走两步, 慢指针每次走一步
  fast = fast.next.next; slow = slow.next;
• 链表结束条件: 快指针走的快, 当快指针走完链表, 即遍历结束
  while(fast != null && fast.next != null);

4.代码详解

class Solution {public ListNode middleNode(ListNode head) {// 定义快慢指针ListNode slow = head;ListNode fast = head;// fast 为空或 fast.next 为空则跳出循环while (fast != null && fast.next != null) {// slow 走一步slow = slow.next;// fast 走两步fast = fast.next.next;}// 返回中间节点return slow;}
}

四.输出链表的倒数第k个节点

1.题目描述 ----- 面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

给定的 k 保证是有效的。

2.思路分析

思路分析: 快慢指针

快指针先走k步后, 此时快慢指针的差距是k步, 然后快慢指针一起走, 快指针走完链表后, 慢指针走到倒数第k个位置处

3.算法过程

• 定义快慢指针
  fast = head; slow = head;
• 快指针先走k步
  for(i = 0; i < k; i++) fast = fast.next;
• 快慢指针一起走,快指针走完,慢指针到倒数第k个位置处
  while(fast != null) fast = fast.next; slow = slow.next;
• 返回倒数第k个位置处的值 return slow.val;

4.代码详解

class Solution {public int kthToLast(ListNode head, int k) {// 定义快慢指针ListNode slow = head;ListNode fast = head;// 让 fast 先走 k 步for (int i = 0; i < k; i++) {fast = fast.next;}// 此时，fast 已经领先 slow k 步// 两个一起走，当 fast 到达最后一个节点的时候，slow 走到第 k 个节点while (fast != null) {fast = fast.next;slow = slow.next;}// 返回 slow 处的值return slow.val;}
}

五.合并有序链表

1.题目描述 ----- 21. 合并两个有序链表 - 力扣（LeetCode）

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1  l2  非递减顺序 

2.思路分析

思路分析: 模拟

比较节点的大小, 那个值小则把该节点放到connection链表的后面, 那个链表为空后, 则把另一个链表放在connection的后面;

3.算法过程

• 定义连接节点和新的头节点
  connection = new ListNode(); head = connection;
• 循环遍历, 当list1和list2均空则跳出循环
  • list1为空, 则把list2的所有节点放到connection的后面, 跳出循环
    connection.next = list2; break;
  • list2为空, 则把list1的所有节点放到connection的后面, 跳出循环
    connection.next = list1; break;
  • 若list1.val < list2.val
    connection.next = list1;
    list1 = list1.next; //后移
    connection = connection.next; //后移
  • 若list1.val > list2.val
    connection.next = list1;
    list1 = list1.next; //后移
    connection = connection.next; //后移
• 返回头节点 return head.next;

4.代码详解

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 其中一个链表为空if (list1 == null) return list2;if (list2 == null) return list1;// 定义连接链表ListNode dummy = new ListNode();// 定义新的头节点ListNode newHead = dummy;// 当 list1 和 list2 均为空，跳出循环while (list1 != null || list2 != null) {if (list1 == null) {// list1 为空，把 list2 的节点全部放在 dummy 后面dummy.next = list2;break;} else if (list2 == null) {// list2 为空，把 list1 的节点全部放在 dummy 后面dummy.next = list1;break;} else if (list1.val < list2.val) {// list1 节点值小于 list2 节点值，把 list1 的节点放在 dummy 后面dummy.next = list1;// 让 list1 走到下一个节点处list1 = list1.next;} else {// list2 节点值小于 list1 节点值，把 list2 的节点放在 dummy 后面dummy.next = list2;// 让 list2 走到下一个节点处list2 = list2.next;}// 让 dummy 走到下一个节点处dummy = dummy.next;}// 返回头节点return newHead.next;}
}

六.分割链表

1.题目描述 ----- 面试题 02.04. 分割链表 - 力扣（LeetCode）

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

• 链表中节点的数目在范围 [0, 200] 
• -100 <= Node.val <= 100
• -200 <= x <= 200

2.思路分析

思路分析: 模拟

• 定义四个链表, minVal链表存储比x小的节点, maxVal链表存储比x大的节点;
  minHead指向minVal, maxHead指向maxVal
• 循环head链表, 把比x小的节点放入到minVal链表中, 比x大的节点放入到maxVal链表中
• 防止形成环, 把maxVal.next置为空, 因为最大的值不一定是最后一个
• 连接两个链表, 并返回新链表的头节点

3.算法过程

• 创建两个链表,定义头节点 minVal, maxVal = new ListNode();
  minHead = minVal; maxHead = maxVal;
• 循环head链表, 把节点值小于x的放到minVal中, 比x大的放入到maxVal中
  if(cur.val < x) minVal.next = cur; minVal = minVal.next;
  else maxVal.next = cur; maxVal = maxVal.next;
• 把maxVal的next置为空, 防止形成环
  maxVal.next = null;
• 连接两个链表
  minVal.next = maxHead.next;
• 返回新链表 return minHead.next;

4.代码详解

class Solution {public ListNode partition(ListNode head, int x) {// 使用 prev 来获取小于 x 值的链表节点ListNode prev = new ListNode();// 指向 prev 的节点，用于后续返回结果ListNode newHead = prev;// 使用 last 来获取 大于等于 x 值的链表节点ListNode last = new ListNode();// 使用 headLast来指向 last 的头节点，方便连接ListNode headLast = last;// 遍历链表节点ListNode cur = head;// 为空跳出循环while (cur != null) {// 小于 x 的链表节点值的节点都放在 prev 链表下if (cur.val < x) {prev.next = cur;prev = prev.next;} else {// 大于等于 x 的链表节点值的节点都放在 last 链表下last.next = cur;last = last.next;}// cur 获取下一个节点cur = cur.next;}// 防止 last 的最后一个节点不是链表的最后一个节点last.next = null;// 连接prev.next = headLast.next;// 返回return newHead.next;}
}

七.回文链表

1.题目描述 ----- LCR 027. 回文链表 - 力扣（LeetCode）

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

• 链表 L 的长度范围为 [1, 10^5]
• 0 <= node.val <= 9

2.思路分析

思路分析: 快慢指针 + 头插法 + 前后指针比较

• 定义快慢指针, 找到中间节点
• 把中间节点之后的元素都进行头插
• 使用slow指针和fast指针比较值, 不同则不是回文

3.算法过程

• 定义快慢指针
  fast = head; slow = head;
• 循环链表, 快指针每次走两步, 慢指针每次走一步, 找到中间节点
  fast = fast.next.next; slow = slow.next;
• 在中间节点进行头插
  curNext = cur.next;
  cur.next = slow;
  slow = cur;
  cur = curNext;
• 重置快指针, 快慢指针相等则说明为回文链表
  fast = head;
  while(fast != slow)
  if(fast.val != slow.val) return false;
  if(fast.next == slow) return true; // 偶数个节点
• 跳出循环, 说明是回文链表 return true;

4.代码详解

class Solution {public boolean isPalindrome(ListNode head) {// 定义快慢指针ListNode fast = head;ListNode slow = head;// fast 为空或 fast.next为空跳出循环while(fast != null && fast.next != null) {// fast 每次走两步fast = fast.next.next;// slow 每次走一步slow = slow.next;}// 头插// 把 slow 后面的节点进行头插ListNode cur = slow.next;while(cur != null) {// 记录 cur 的下一个节点ListNode curNext = cur.next;// 头插cur.next = slow;// 重置头节点slow = cur;// 获取下一个节点cur = curNext;}// 重置 fastfast = head;// 当相遇时跳出循环，说明是回文链表while(fast != slow) {// 值不相等则说明不是回文链表if(fast.val != slow.val) {return false;}// 节点为偶数个的回文链表if(fast.next == slow) {break;}// fast 和 slow 均走一步fast = fast.next;slow = slow.next;}// 返回结果return true;}
}

八.链表的公共节点

1.题目描述 ----- 160. 相交链表 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

• listA的数目为 m
• listB的数目为n
• 1 <= m, n <= 3 * 10^4
• 1 <= Node.val <= 10^5
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA  和listB 没有交点, intersectVal 为0

• 如果 listA  和listB 有交点, intersectVal == listA[skipA] == listB[skipB] 

2.思路分析

思路分析: 模拟.

获取两个两个链表的长度, 判断出谁长, 使用一个引用指向最长的那个链表, 另一个引用指向最短的那个链表;让最长的那个链表先走两个链表的差值步, 然后两个一起走, 即可得到相遇点

3.算法过程

• 获取两个链表的长度
  l1 = size(A); l2 = size(B);
• 区分最长和最短的链表, 获取两者的差值步
  cur1 = 最长的链表; cur = 最短的链表; gap = size(长链表) - size(短链表);
• 让最长的链表先走两者的差值步
  for(int i = 0; i < gap; i++) cur1 = cur1.next;
• 长短链表一起走, 相遇即是相遇点
  while(cur1 != cur2) cur1 = cur1.next; cur2 = cur2.next;
• 返回相遇点 return cur1;

4.代码详解

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// cur1 用来指向长度最长的链表，默认是 headAListNode cur1 = headA;// cur2 用来指向长度最短的链表，默认是 headBListNode cur2 = headB;// 计算两个链表的长度int size1 = count(headA);int size2 = count(headB);// 用来获取两个链表的长度差int gap = 0;if (size1 > size2) {// 这个地方说明 headA 的链表长度最长// 计算两个链表的长度差即可gap = size1 - size2;} else {// 这个地方说明 headB 的链表长度最长// 重置 cur1 和 cur2，让他们分别指向最长和最短的链表cur1 = headB;cur2 = headA;// 链表长度的差值gap = size2 - size1;}// 让最长的链表先走差值步for (int i = 0; i < gap; i++) {cur1 = cur1.next;}// 两个链表一起走，相等则说明走到了公共节点while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}// 返回公共节点return cur1;}// 计算链表的节点数private int count(ListNode head) {int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}
}

九.判断链表是否有环

1.题目描述 ----- 141. 环形链表 - 力扣（LeetCode）

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

• 链表中节点的数目范围是 [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos 为 -1 或 有效索引 

2.思路分析

思路分析: 快慢指针.

让快指针每次走两步, 慢指针每次走一步; 若是存在环, 那么两者必会相遇, 若不存在环, 则跳出循环, 返回false

3.算法过程

• 判断head是否有节点
  if(head == null) return false;
• 定义快慢指针
  fast = head; slow = head;
• 循环遍历快指针, 快指针每次走两步, 慢指针每次走一步, 无环则会跳出循环, 有环则会相遇
  fast = fast.next.next; slow = slow.next;
• 无环跳出循环后返回false return false;

4.代码详解

public class Solution {public boolean hasCycle(ListNode head) {// 初始化快慢指针ListNode slow = head;ListNode fast = head;// 判断快指针当前是否为空或快指针的下一个节点是否为空while (fast != null && fast.next != null) {// fast每次走两步fast = fast.next.next;// slow每次走一步slow = slow.next;// 相等, 遇到环if (fast == slow)return true;}// 不存在环return false;}
}

思考: 一定要快指针每次跳两步, 慢指针跳一步嘛? 快指针一次跳三步或四步可行嘛?

解释: 两个节点的有环链表画图能理解为什么要只走两步

十.链表的入环点

1.题目描述 ----- 142. 环形链表 II - 力扣（LeetCode）

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

• 链表中节点的数目范围在范围 [0, 10^4] 
• -10^5 <= Node.val <= 10^5
• pos  为-1或为一个有效的索引 

2.思路分析

思路分析: 快慢指针

让快指针每次走两步, 慢指针每次走一步; 相遇后跳出循环, 然后让快指针回溯到head节点的位置, 快慢指针一起走, 相遇点即为入环点

3.算法过程

• head判空
  if(head == null) return head;
• 定义快慢指针,快指针每次走两步, 慢指针每次走一步, 相遇跳出循环
  fast = fast.next.next; slow = slow.next; if(fast == slow) break;
• 判断无环的情况
  if(fast == null || fast.next == null) return null;
• fast重指向head fast = head
• fast和slow一起走, 相遇点即为入环点
  while(fast != slow) fast = fast.next; slow = slow.next;
• 返回入环点 return fast;

4.代码详解

public class Solution {public ListNode detectCycle(ListNode head) {// 一个节点也没有if (head == null) return null;// 定义快慢指针ListNode slow = head;ListNode fast = head;// fast 不为空或 fast.next 不为空while (fast != null && fast.next != null) {// fast 每次走两步fast = fast.next.next;// slow 每次走一步slow = slow.next;// 相遇跳出循环if (fast == slow) {break;}}// 两种情况// 1.无环的情况下，会跳出循环// 2.有环的情况，相遇后跳出循环// 这里判断无环的情况if (fast == null || fast.next == null) {return null;}// 重置快指针fast = head;// 快慢指针相遇点即为入换点while (fast != slow) {fast = fast.next;slow = slow.next;}// 返回入环点return fast;}
}