目录

• • 1. 删除链表中等于给定值val的所有结点
  • 2. 逆置单链表
  • 3. 链表的中间结点
  • 4. 链表中倒数第k个结点
  • 5. 将两个有序链表合并为一个新的有序链表
  • 6. 以给定值x为基准将链表分割成两部分
  • 7. 判断是否为回文链表
  • 8. 两个链表的第一个公共结点
  • 9. 判断链表中是否有环
  • 10. 链表开始入环的第一个节点

1. 删除链表中等于给定值val的所有结点

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

思路：由于需要进行删除结点，在链表中删除结点，要知道该结点的前一个结点，因此定义2个结点pre和cur，pre表示cur的前一个结点。【pre和cur的关系】
在此循环过程中，一直没有判断pre的值是否等于val，所有可以在一开始就判断头结点的值是否为val，直至头的值不为val为止。

代码：

       while (head !=null && head.val == val) {head = head.next;}if (head == null) {return null;}ListNode pre = head;ListNode cur = head.next;while (cur != null) {if (cur.val != val) {pre = pre.next;cur = cur.next;}else {pre.next = cur.next;cur = cur.next;}}return head;

2. 逆置单链表

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

思路：
①如果链表没有结点或者只有一个结点，那么不用逆置，直接返回head头结点；
②弄清楚head、cur、curNext三者之间的关系，没翻转之前head在cur的前面，那么翻转之后cur的下一个结点就是head，翻转完成之后，再给head、cur、curNex重新赋值。即cur表示正要逆置的结点，与head进行逆置，curNext表示下一个将要逆置的结点。

代码：

    public ListNode reverseList(ListNode head) {if (head == null || 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;}

3. 链表的中间结点

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

思路：快慢指针，快的每次走2步，慢的每次走1步，要考虑结点个数为奇数和偶数个的情况。s = v * t，路程等于速度乘以时间，t相同，快指针的v是慢指针的v的2倍，所以当快指针走完链表的时候，慢指针的s是快指针的一半，即为链表的中间结点。

代码：

    public ListNode middleNode(ListNode head) {if (head == null) {return null;}ListNode slow = head;ListNode fast = head;while (fast != null && fast.next !=null) {slow = slow.next;fast = fast.next.next;}return slow;}

4. 链表中倒数第k个结点

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

思路：本题不用考虑k值不合法的情况【快慢指针】
让快的指针先走k步，之后，快的走一步，慢的走一步，最后当快的为空的时候，慢指针所指的结点即为倒数第k个结点。

代码：

class Solution {public int kthToLast(ListNode head, int k) {ListNode slow  = head;ListNode fast = head;while (k > 0) {fast = fast.next;k--;}while (fast != null) {slow = slow.next;fast = fast.next;}return slow.val;}
}

5. 将两个有序链表合并为一个新的有序链表

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

思路：新建一个头结点，用于拼接合并后的链表。当有一个链表走完的时候结束循环，最后直接把没走完的链表拼接在新链表的末尾就可以。

代码：

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead = new ListNode();ListNode cur = newHead;while (list1 != null && list2 != null) {if (list1.val < list2.val) {cur.next = list1;cur = cur.next;list1 = list1.next;}else {cur.next = list2;cur = cur.next;list2 = list2.next;}}if (list1 != null) {cur.next = list1;}if (list2 != null) {cur.next = list2;}return newHead.next;}

6. 以给定值x为基准将链表分割成两部分

力扣面试题 02.04. 分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。

思路：基准左边的链表，头结点为bb（before begin），尾结点为be（before end）；基准右边的链表，头结点为ab（after begin），尾结点为ae（after end）
遍历原链表上，与基准值进行比较，如果比基准值小就放到bb和be链表上，反之放到ab和ae链表上，大体思路是最后返回bb，但还有细节需要处理。
①：前半段bb和be为空，即没有比基准小的元素，不需要进行前后拼接，那么直接返回后半段链表，即ab
②后半段ab和ae为空，不需要进行前后拼接，直接返回前半段链表，即bb
③前后都不为空，则需要将前半段尾结点be连上ab，并且后半段尾节点的指向置为空。

代码：

class Solution {public ListNode partition(ListNode head, int x) {if (head == null) {return null;}ListNode bb = null;ListNode be = null;ListNode ab = null;ListNode ae = null;while (head != null) {if (head.val < x) {if (bb == null) {bb = head;be = head;}else {be.next = head;be = be.next;}}else {if (ab == null) {ab = head;ae = head;}else {ae.next = head;ae = ae.next;}}head = head.next;}if (be == null) {return ab;}else {if (ae !=null) {be.next = ab;ae.next = null;}return bb;}}
}

7. 判断是否为回文链表

力扣面试题 02.06. 回文链表
编写一个函数，检查输入的链表是否是回文的。

思路：
①寻找链表的中间结点（快慢指针）
②将中间节点的后面链表进行逆置（3个结点之间的关系）
③前后遍历节点值是否相等
从后往前遍历的相等终止条件是head和mid相遇了（奇数个结点）或者head的下一个结点就是mid（偶数个结点）

代码：

class Solution {public boolean isPalindrome(ListNode head) {if (head == null) {return true;}//先找中间结点ListNode mid = finMid(head);//逆置后面的结点ListNode cur = mid.next;while (cur != null) {ListNode curNext = cur.next;cur.next = mid;mid = cur;cur = curNext;}while (head != null) {if(head.val != mid.val) {return false;}if (head == mid || head.next== mid) {return true;}head = head.next;mid = mid.next;}return false;}private ListNode finMid(ListNode head) {//快慢指针ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}

8. 两个链表的第一个公共结点

力扣160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

思路：如果2个链表有公共的结点，那么一定是“Y”型的，后面的结点元素个数一定相等，那么不同的就是前面部分，让长度长的链表先走比长度短的结点的长度差的长度，之后两个一步一步走，并且判断两个结点是否相等。
【注意】公共结点是指结点相等，不是结点值相等。

代码：

public class Solution {private int getLen(ListNode head) {ListNode cur = head;int len = 0;while (cur != null) {cur = cur.next;len++;}return len;}//相交结点public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int len1 = getLen(headA);int len2 = getLen(headB);ListNode p1 = headA;ListNode p2 =headB;if (len1 > len2) {int size = len1 - len2;while (size > 0) {p1 = p1.next;size--;}}else {int size = len2 - len1;while (size > 0) {p2 = p2.next;size--;}}while (p1 != p2) {p1 = p1.next;p2 = p2.next;}if (p1 != null) {return p1;}else {return null;}}
}

9. 判断链表中是否有环

力扣141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路：快慢指针，快指针走2步，慢指针走1步，然后看两个指针能否再次相遇。

【判断环的问题实际上是数学上的“追击”问题】
思考：为什么快的走2步，慢的走1步就可以相遇呢？
答：如果快的走3步、4步等，那么可能快慢指针就无法相遇，并且有可能出现空指针异常。
快慢指针2步1步的话，可以使两者之间的距离在进入环之后，每次缩小一步，不会出现套圈的情况，快指针肯定使可以追上慢指针的。
代码：

public class Solution {public boolean hasCycle(ListNode head) {if (head == null) {return false;}ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return false;}
}

10. 链表开始入环的第一个节点

力扣142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

思路：一个指针从链表起始位置开始走，一个指针从相遇点的位置开始环绕，每次都只走1步，最后两个指针会在入口点的位置相遇。

代码：

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null) {return null;}ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (fast == slow) {break;}}if (fast == null || fast.next == null) {return null;}fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}
}