一、删除链表中重复的结点
1. 牛客网 JZ76
题目要求：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的节点对应的 val 值是相同的，而且是连在一起的。重复的结点不保留，返回链表头指针。例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5.
2. 代码实现
public class Solution { public ListNode deleteDuplication(ListNode head) { if(head == null){ return null; } ListNode newhead = new ListNode(-1); //最终返回的是 newhead, 所以这里我们只能让 temp 去跑 ListNode temp = newhead; ListNode cur = head; while(cur != null){ if(cur.next != null && cur.val == cur.next.val){ while(cur.next != null && cur.val == cur.next.val){ cur = cur.next; } cur = cur.next; }else{ temp.next = cur; temp = temp.next; cur = cur.next; } } temp.next = null; return newhead.next; } }
3. 代码分析
思路：
那么我们先从正常情况下入手：
（1）创建一个 cur 指针用来遍历链表
（2）创建一个傀儡节点 newhead
cur指针遍历的时候，就开始判断 cur.val 与 cur.next.val 的关系，重复的节点就使用 while 循环进行跳过，为什么要用循环呢？因为重复的节点可能不止 2 个，可能会有 3 个，4 个…而我们也要让 cur 同步往前走，所以只能选择循环了。此时我们在循环之后，还要加上 [ cur = cur.next; ] 这行代码。因为循环过后，我们的 cur 指针一定要判断下一个节点对应的 val。
而非重复的节点，就用 newhead 节点将他们串起来，也就是如下代码。
if(cur.val == cur.next.val){ while(){ } }else{ }
而我们不能写成
if(cur.val != cur.next.val){ }else{ while(){ } }
因为当 cur 遍历到最后一个节点的时候，如果 cur.val 是非重复的节点，而我们 cur.next == null，就会令 cur.next.val 造成空指针异常，但是，这时候，此时的最后一个节点是我们必须要串联起来的的，所以就只能这么考虑。这在我下图分析的时候，会提到。
经过以上分析，对于正常情况下，我列出几个要点：
① 头节点为 null 时，返回 null
② 判断重复节点的时候，用 if；判断非重复节点的时候，用 else
③ 在使用 while 循环跳过所有的重复节点的时候，我们要注意 cur 的落脚点
④ 在串联完所有的节点后，尾节点中的指针域要置成 null
⑤ return 返回的时候，头结点位置在哪
经过上面的分析我们一定会写出如下代码，但是系统一定会报空指针异常的错误。
while(cur != null){ if(cur.val == cur.next.val){ while(cur.val == cur.next.val){ cur = cur.next; } cur = cur.next; }else{ temp.next = cur; temp = temp.next; cur = cur.next; } } temp.next = null; return newhead.next;
现在我们开始纠正错误，并讨论特殊情况，问题出在了这两行代码：
if(cur.val == cur.next.val){ while(cur.val == cur.next.val){
请看我分析：
特殊情况①：链表中只有一个节点
特殊情况②：链表的最后一个节点属于重复节点
所以我们将这两行代码改成
if(cur.next != null && cur.val == cur.next.val){ while(cur.next != null && cur.val == cur.next.val){
这样一来，如果真的碰到了特殊情况，直接就走 else，或者直接退出外层的 while 循环。
我刚开始做这道题，还是很懵的，因为这题需要的时间复杂度是 O(N)，也就是说我们只能遍历链表一次，所以情况还是较为复杂的，因为我们有许多细节要考虑，主要就是循环和分支的条件。
二、链表的回文结构
1. 牛客网 OR36
题目要求：对于一个链表，请设计一个时间复杂度为O(n)，额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。
牛客网 OR36
2. 代码实现
public class PalindromeList { public boolean chkPalindrome(ListNode head) { //1. 创建快慢指针走到中间位置 ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } //2. 链表反转 ListNode cur = slow.next; while(cur != null){ ListNode cur2 = cur.next; cur.next = slow; slow = cur; cur = cur2; } //3. 判断回文结构 ListNode right = slow; ListNode left = head; while(left != right){ if(left.val != right.val){ return false; } if(left.next == right){ return true; } left = left.next; right = right.next; } return true; } }
3. 代码分析
思路：
步骤（1）：创建快慢指针 fast 和 slow，定位到中间位置。
此步骤在上一篇博客中有介绍到，即求链表的中间节点，这里不再赘述。
ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; }
步骤（2）：中间位置之前链表指向不变，中间位置之后，链表指针反转。
此步骤在上一篇博客中有介绍到，即求链表反转，这里同样不再赘述。
ListNode cur = slow.next; while(cur != null){ ListNode cur2 = cur.next; cur.next = slow; slow = cur; cur = cur2; }
步骤（3）：创建两个指针 left 和 right，不断向中间靠拢，进行回文结构的判断。
left != right 的时候，就一直循环，当左边的某个值和右边的某个值对应不相等的时候，就说明，不是回文链表，那么就返回 false，如果对应相等，那么两个指针不断向中间靠拢，直到遇到同一个节点，循环停止。
版权声明：本文为CSDN博主「十七ing」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
while(left != right){ if(left.val != right.val){ return false; } left = left.next; right = right.next; } return true;
然而，过程并不是那么顺利的，还有一个特殊情况，那就是链表中存在节点的数量是偶数。比如说：上面三个步骤讨论的是节点数量为 5 的时候，下面我们看看当节点数量为 4 的时候，会发生什么情况？
由于不管节点的数量是奇数还是偶数，上述的步骤（1）和步骤（2）的情况都是一样的，所以我们着重分析步骤（3），也就是判断回文结构。
请读者仔细阅读上图，也就是说，在 while 循环走的过程中，指针 left 和 right 不断地向中间靠拢，当 left.next == right 的时候，此时的循环停下，也就满足回文结构，这是链表的节点数为偶数的一种情况。代码实现如下：
此时，读者请再思考一个问题
if(left.next == right) //能不能写成 if(left == right.next)
答案是否定的，因为在我们步骤（1）中，使用快慢指针的时候，就已经确定了 slow 的位置。
读者可以回过头看看上图，当节点数为 4 的时候，前半段有两个白色的箭头，后半段只有一个绿色的箭头。
这就造成了，当我们使用 right.next 的时候，我们发现，其实 right.next 不指向任何地方！这个细节也是很关键的。读者感兴趣的话，可以试试当节点数为 6 的时候，此规律也适用。
三、找出两链表的公共节点
1. leetcode 160
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交节点。如果两个链表不存在相交节点，返回 null 。
2. 代码实现
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //如果其中一个链表为null，那么肯定没有相交的节点 if(headA == null || headB == null){ return null; } //始终默认cur1指向长度最长的链表，cur2指向长度最短的链表 ListNode cur1 = headA; ListNode cur2 = headB; int len1 = 0; int len2 = 0; while(cur1 != null){ cur1 = cur1.next; len1++; } while(cur2 != null){ cur2 = cur2.next; len2++; } //当两个遍历走完，那么cur1和cur2必定为null //此时我们应该重新让两个指针指向各自的头部 cur1 = headA; cur2 = headB; //记录一下两个链表相差的步数 int step = len1 - len2; //当步数＜0时，将指向长短链表的头指针互换 if(step < 0){ cur1 = headB; cur2 = headA; step = len2 - len1; } //让长链表对应的cur1先走 step 步 for(int i=0; i<step; i++){ cur1 = cur1.next; } while(cur1 != cur2){ cur1 = cur1.next; cur2 = cur2.next; //如果将某个链表中的所有节点都走完了, //那么就说明两节点之间没有公共节点 if(cur1 == null || cur2 == null){ return null; } } return cur1; } }
3. 代码分析
思路：
（1）将 cur1 这个指针定义为始终指向长度最长的那个链表，将 cur2 这个指针定义为永远指向长度最短的那个链表。
（2）分别遍历链表 A 和链表 B，通过step = len1 - len2，记录长度。当 step > 0 的时候，那么链表 A 为长链表，链表 B 为短链表，那么我们就先让 cur1 先走 step 步，而 cur2 保持不动；接着 cur1 和 cur2 就能同步往下走了，直至遇到公共节点，就停下来。当 step < 0 的时候，将 cur1 和 cur2 交换一下就行了。这里应该注意的是：当 cur1 和 cur2 分别遍历完链表的时候，我们应该将他们分别置成原先的链表头。
上述是正常情况下有公共节点，而下面是无节点的情况。
四、判断链表是否有环
1. leetcode 141
题目要求：给你一个链表的头节点 head ，判断链表中是否有环。
2. 代码实现
public class Solution { public boolean hasCycle(ListNode head) { //当链表为空或者链表只有一个节点的时候，直接返回 false if(head == null || head.next == null){ return false; } ListNode fast = head; ListNode slow = head; //为了防止空指针异常，设置好循环条件 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ return true; } } return false; } }
3. 代码分析
思路：
（1）创建快慢指针 fast 和 slow，fast 一次走两步，slow 一次走一步，两者同时进行，至于循环的条件，和上一篇的博客（找到链表的中间节点）的思想是一样的。
（2）当 fast 和 slow 相遇的时候，那么就证明链表有环，反之，链表无环。
注意：请读者思考一下，我让 fast 一次走三步，slow 一次走一步，这能达到验证链表有环的结果吗？
fast = fast.next.next.next; slow = slow.next;
答案是否定的，请看上面的例子：当链表是由两个无环的节点构成，那么会出现空指针异常。这个时候，我们应当在 while 循环加上 （&&fast.next.next != null），这样就不会报错了！读者感兴趣的话，可以自己模拟一下上述情况，很有意思~
然而，因为我们编写的程序就是要符合每一种情况的，不仅要考虑到可行的，也要考虑到不可行的。所以以越简洁越好。综上所述，我们不可能再去探索 fast 一次走4步，5步…因为 fast 一次走两步，已经达到要求。
五、环形链表的入口节点
1. leetcode 142
题目要求：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null.
2. 代码实现
public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next == null){ return null; } ListNode fast = head; ListNode slow = head; int flag = 0; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ flag = 1; //相遇的标志用flag记下来 break; } } if(flag == 0){ //如果 flag为0，就代表链表无环 return null; } ListNode start2 = slow; ListNode start1 = head; while(start1 != start2){ start1 = start1.next; start2 = start2.next; } return start1; //start1和start2相遇的节点就是入口点 } }
3. 代码分析
（1）先判断链表是否有环，此过程不再赘述，与上一题重复，此外，flag 当作标志。
（2）如果有环，记录 fast 和 slow 相遇节点的指针为 start2，记录 head 为 start1，让 start1 和 start2 同步走，当start1 和 start2 相遇了，就是我们要找的节点。
相信很多人对第（2）步感到匪夷所思，这是通过公式推导出来的
fast走过的路程：a+b+n(b+c) // [ n 表示走过环的圈数 ] slow走过的路程：a+b (其中：c 和 n 完全可能为0) 由于 fast 走过路程是 slow 走过路程的两倍，所以有 a+b+n(b+c) = 2(a+b) => a = (n-1)b+nc => a = (n-1)(b+c)+c //上述公式说明一个关键点：不论(n -1)为多少，都证明(n-1)(b+c)只是重复的圈数 //而我们本题求的是入口节点的位置，所以我们只要记住： =>a=c //也就是说，头节点到入口点的路程 = 相遇点到入口点的路程。
下图辅助理解
Over. 谢谢观看哟~
