目录
1.删除链表中等于给定值val的所有节点
2.反转一个单链表
3.给定一个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
4.输入一个链表，输出该链表中倒数第k个结点
5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
7. 链表的回文结构
8. 输入两个链表，找出它们的第一个公共结点
9. 给定一个链表，判断链表中是否有环
10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
1.删除链表中等于给定值val的所有节点 迭代：

public ListNode removeElements(ListNode head, int val) { if(head == null) return null; //处理头 while(head != null && head.val == val) { head = head.next; }//处理中间和尾巴 ListNode cur = head; if(cur != null) { while(cur.next != null) { if(cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } } return head; }

1.处理头：写在前面就要写成循环，因为前两个或前面有 >=2 个待删除的元素时，一个if条件语句是解决不了的，而且条件必须包含head不为空，因为在删除的过程中，head一直在往后走，防止出现空指针异常如果要用 if，则需要写在后面。
2.处理中间为尾巴：看下图

文章图片

递归：

public ListNode removeElements(ListNode head, int val) { if (head == null) return head; //先递归到最后一个结点，然后用上一次递归的head的next域接收 head.next = removeElements(head.next, val); //如果此时的head的val是要删除的元素，即返回它的next return head.val == val ? head.next : head; }

注释看不明白的话，下图作为辅助理解：

文章图片

2.反转一个单链表
文章图片

public ListNode reverseList(ListNode head) { if(head == null) return null; //处理一个结点的情况 if(head.next == null) return head; ListNode pre = null; while(head != null) { ListNode headNext = head.next; head.next = pre; pre = head; head = headNext; } return pre; }

思路：

【java|10道经典链表面试题】做这个题的时候，我们需要两个额外的"指针"，一个用来保存 head 的地址，一个用来保存head.next 的地址，因为每次都需要把自己的next域改为前一个结点的地址，然后不断往后走，直到 head 为空，，，

图解：

文章图片

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

public ListNode middleNode(ListNode head) { if(head == null) return null; //if(head.next == null) return head; ListNode fast = head; //一次走两步 ListNode slow = head; //一次走一步 //循环条件是把两种情况 && 在了一起 while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; }

解题中需要注意的点：

1.我们定义快慢指针，最初都指向head，然后一个走一步，一个走两步---》路程相同，fast的速度是slow的两倍，当，fast到终点的时候，slow一定在路程的中间；
2.我们需要分情况讨论，分别是：奇数个结点和偶数个结点两种情况；
3.两种情况让循环终止的条件必须 && 在一起，根据短路原理，因为只可能存在两种情况中的一种，而我们又不知道具体是哪一种情况，所以一个条件不满足，就要让循环终止。

图解：

文章图片

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

public ListNode FindKthToTail(ListNode head,int k) { if(head == null) { return null; } //判断 k 的合法性 if(k <= 0) { return null; }ListNode fast = head; ListNode slow = head; //先让 fast 走 k-1 步 while(k - 1 > 0) { fast = fast.next; if(fast == null) { return null; } k--; } //在一起往后走 while(fast.next != null) { fast = fast.next; slow = slow.next; } return slow; }

这个题和找链表的中间结点异曲同工，主要注意的点就是返回倒数第 K 个结点的时候，此时的 fast 与 slow 之间相差 K - 1 步，所以我们的思路就是先让 fast 走 K - 1 步，然后再一起走，直到fast走到最后一个结点，，，

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

public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null && list2 == null) return null; if(list1 == null) return list2; if(list2 == null) return list1; //我创建一个新的空结点，两链表互相从头开始比较，把较小的接在新的结点后面 ListNode newHead = new ListNode(0); ListNode cur = newHead; //有一个为空就退出循环 while(list1 != null && list2 != null) { if(list1.val < list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } //循环走到这里，一定有一个链表为空 cur.next = list1 == null ? list2 : list1; return newHead.next; }

思路：

1.我们 new 一个空结点，作为新的链表的头，然后循环不断比较两个链表的值，把较小的一个接在新的头后面，直到其中一个链表为空，就退出循环，，，
2.退出循环时，一定有一个链表为空，此时就把不为空的链表接在新链表尾结点的 next 域；

图解：

文章图片

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
文章图片

public ListNode partition(ListNode pHead, int x) { //申请两个头和尾，小于x的放bs,be，其余的放在as,ae; ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = pHead; while(cur != null) { if(cur.val < x) { if(bs == null) { bs = cur; be = cur; } else { be.next = cur; be = cur; } } else { if(as == null) { as = cur; ae = cur; } else { ae.next = cur; ae = cur; } } cur = cur.next; } //如果小的数据这一边为空，直接返回大的数据这一边的头 if(bs == null) { return as; }be.next = as; if(ae != null && ae.next != null) { ae.next = null; } return bs; }

思路：

我们申请两个独立的链表，并都赋予头和尾，把小于x值的全部放在一个链表中，大于x的值全部放在一个链表中，如果都不为空，就把小的链表的尾的next指向大的链表的头，如果小的链表为空，需要单独处理，再一个要注意的点是：大的链表的尾巴可能不为空，所以我们要将其置为空。

图解：

文章图片

7. 链表的回文结构
文章图片

public boolean chkPalindrome(ListNode A) { if(A == null) { return false; } //只有一个结点也是回文结构 if(A.next == null) { return true; } //1.先走到中间结点。2.再反转右边的 ListNode fast = A; ListNode slow = A; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } //反转 ListNode cur = slow.next; while(cur != null) { ListNode curNext = cur.next; cur.next = slow; slow = cur; cur = curNext; } //一个从头走，一个从尾走 while(A != slow) { if(A.val != slow.val) { return false; } if(A.next == slow) { return true; } A = A.next; slow = slow.next; } return true; }

思路：

1.我们用快慢指针，找到链表的中间结点
2.把中间结点的右半部分反转
3.反转后的 slow 此时指向链表尾结点，然后让头节点 A 和尾结点 slow 同时一步一步走
4.考虑奇数和偶数两种情况，奇数情况两结点一定会相遇，偶数结点，两结点不会相遇，但是会出现在两个中间结点，所以要加上 if 条件判断一下，否则 slow 又往回走了，，，

图解：

文章图片

8. 输入两个链表，找出它们的第一个公共结点
文章图片

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) return null; int lenA = 0; int lenB = 0; ListNode fast = headA; //指向较长的链表 ListNode slow = headB; //指向较短的链表//分别求两链表的长度 while(fast != null) { lenA++; fast = fast.next; } while(slow != null) { lenB++; slow = slow.next; } //重新指回头节点 fast = headA; slow = headB; //如果 len < 0 就把 fast 改为指向长的链表 int len = lenA-lenB; if(len < 0) { fast = headB; slow = headA; len = lenB-lenA; } //先让长的链表走差值步 while(len != 0) { fast = fast.next; len--; } //if(fast == null) return null; //长链表走完差值步，再和短链表一起走 while(fast != slow) { fast = fast.next; slow = slow.next; } return slow; }

思路：

考虑两链表的长度，长度相同就不用处理，主要是长度不相同的情况，我们首先要分别计算两链表的长度，然后让长的链表先走差值步，然后再一起走，相遇的时候，返回即可。

图解：

文章图片

9. 给定一个链表，判断链表中是否有环
文章图片

public static boolean hasCycle(ListNode head) { //空和一个结点都不成环 if(head == null || head.next == null) return false; //两结点初始指向不能相同，否则循环进不去 ListNode fast = head.next.next; ListNode slow = head.next; while(fast != slow) { //快指针走动的过程中，考虑没有环的情况 if(fast == null || fast.next == null) return false; fast = fast.next.next; slow = slow.next; } return true; }

思路：快慢指针

既然一个指针走一步，一个指针走两步能实现，那一个指针走一步，一个指针走三步，走四步，不是可以更块相遇吗？？能否实现？？

答案肯定是不能这样做的，因为两倍速的走，每次都是以一步的距离进行追击，如果三倍速，四倍速的走，巧合的情况下确实可以提高效率，就怕它不巧合，出意外，导致永远都不能相遇；

文章图片

比如这个图：假设 fast 指向1位置，slow 指向2位置，fast 以slow三倍速的走，就永远不会相遇，这里的相遇和生活中的 跑操场追赶 不一样，这里是走的过程中不判断，停下来才判断两指针的指向是否一样。

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

public ListNode detectCycle(ListNode head) { if(head == null || head.next == null) return null; ListNode fast = head.next.next; ListNode slow = head.next; while(fast != slow) { if(fast == null || fast.next == null) { return null; } fast = fast.next.next; slow = slow.next; } //让其中一个指针从头开始走，一个指针从相遇点开始走 slow = head; while(slow != fast) { slow = slow.next; fast = fast.next; } return slow; }

这道题需要推导出一个公式：看完图解基本上就能懂了：

文章图片

不管是大环还是小环，其实我们只要推导出 X = Y 这个公式，让其中一个指针指向 head，另一个指针指向相遇点，两者以相同的速度走，大环的情况，两个指针走的路程分别是 X,Y, 最后在入环点相遇；小环情况，两个指针走的路程分别为 X, (N-1)C, 也就是说，从相遇点开始走的那个指针在小环里面转了很多圈之后，最后走个 Y 的距离就与另一指针相遇了。

谢谢观看！！

推荐阅读

• 

  汽车积碳是什么意思
• 

  redis多节点同步
• 

  27岁有稳定工作,想用20万存款当做第二职业来投资,投资什么好呢？
• 

  上海戏剧学院分数线 2019年上海戏剧学院分数线
• 

  去加拿大必买清单 去加拿大买什么最划算
• 

  室内阳台养什么花最好 室内阳台适合养什么花好
• 

  火理财什么时间可以申请债权转让？债权转让收费吗
• 

  塑料菜板发黑怎么办
• 

  癌细胞|癌细胞已经转移，为什么人的精神依旧很好，而且很能吃？是好事？
• 

  详细步骤及注意事项 g2810加墨水后如何操作
• 

  佳能相机7100 佳能7100单反
• 

  有什么好看的书推荐？
• 

  你喜欢看军事小说吗？
• 

  空气阻尼器时间继电器 空气阻尼器结构图
• 

  2023春节坐高铁需要全程戴口罩吗 2021春节能坐高铁吗
• 

  台高官被问“你有接受过性招待吗
• 

  农村籍独生子女补贴如何领取？四类人无法领取有你吗？
• 

  甲氰菊酯有效是多久 甲氰菊酯药效是几天，水里多久失效
• 

  c语言连接数据库函数 c语言数据库连接池
• 

  有宠app怎么关闭资讯推送通知？有宠app关闭资讯推送通知的方法

• 单向链表及常见面试题和双向链表
• 数据结构|链表常见面试题
• 数据结构|常见的链表面试题
• 数据结构|数据结构之链表+常见面试题
• jenkins|jenkins入门篇（二）
• SSM实现物流管理系统快递
• ssm框架体检管理系统源码+文档
• 适配器模式在 MyBatis 中的妙用，面试可以拿来吹了！
• springboot thymeleaf学生考勤请假管理系统