下面是一些链表的算法题，即包含单链表和环的一些题：
第一题：删除链表中val 的所有节点。
203. 移除链表元素 - 力扣（LeetCode）
这道题的做法主要就是两个结点移动，cur主要去试探看是否自己的指符合val，符合的话pre的引用域为cur的引用域、而且cur往下一个走，不符合的话就pre和cur都往下走，这个在一个循环中，循环的中止条件就是cur为空，这样的话每遇到一个val就可以删除，但是头结点没有判断。所以把除了头节点外与val相同的数据都删除了，最后再判断头结点是不是val就可以了。
class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null){return null;}ListNode pre = head;ListNode cur = head.next;while(cur != null){if (cur.val == val){pre.next = cur.next;cur = cur.next;}else{pre = pre.next;cur = cur.next;}}if (head.val == val){head = head.next;}return head;}
}第二题：反转一个单链表。
206. 反转链表 - 力扣（LeetCode）
这个反转链表重点在cur从head.next开始，然后head是cur的前一个结点，curNext是cur的后一个结点，将cur.next改成前一个结点head，这样就指向前面的结点，然后将这样的操作循环执行直至cur等于空循环才结束。
public ListNode reverseList(ListNode head) {if (head == null){return null;}ListNode cur = head.next;head.next = null;while (cur != null){ListNode curNext = cur.next;cur.next = head;head = cur;cur = curNext;}return head;
}第三题：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
876. 链表的中间结点 - 力扣（LeetCode）
可以通过两倍关系找中间结点，用fast（一次走两步）引用走完全部链表，slow（一次走一步）引用所走到的地方就是中间，所以返回slow，循环条件就是fast为空或者fast.next为空（因为一个链表的长度可能是奇数也可能是偶数）。
public ListNode middleNode(ListNode head) {if (head == null){return null;}ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}第四题：输入一个链表，输出该链表中倒数第k个结点。
链表中倒数第k个结点__牛客网
找倒数第k个结点，可以fast先走k-1步（如果这过程中fast为空的话直接返回空，说明链表的长度小于k），然后slow和fast一起走直到fast.next为空时停止，这是slow位置的结点就是倒是第k个结点。
public ListNode FindKthToTail(ListNode head, int k) {ListNode fast = head;ListNode slow = head;for (int i = 0; i < k; i++){if (fast == null){return null;}fast = fast.next;}while (fast != null) {fast = fast.next;slow = slow.next;}return slow;}第五题：将两个有序链表合并为一个新的有序链表并返回。
21. 合并两个有序链表 - 力扣（LeetCode）
合并两个链表需要头结点和一个添加结点的尾结点，头结点不移动方便遍历链表，尾结点负责添加这两个链表的结点，这样就将两个链表串在一个新的链表中了。合并的主要就是比较两个链表数据，如果list1中的第一个结点更小，就把这个结点连到新的链表中，然后指向下一个结点，再将两链表所指向的数据比大小，小的就加入到新链表中，在这个循环中如果有一个链表为空了，就将剩下链表中的结点都连在新链表中，最后就返回新链表的头结点。
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead = new ListNode();ListNode nextHead = newHead;while (list1 != null && list2 != null) {if (list1.val > list2.val) {nextHead.next = list2;nextHead = nextHead.next;list2 = list2.next;} else {nextHead.next = list1;nextHead = nextHead.next;list1 = list1.next;}}if (list1 != null) {nextHead.next = list1;} else {nextHead.next = list2;}return newHead.next;
}第六题：给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
链表分割_牛客题霸_牛客网
思路在于将链表分成两个链表（一个小于x，一个大于x）， 遍历一遍链表遇到比x小的，通过尾插法将结点加入到新链表中（注意第一次插入时是直接插入），两个链表都有头结点和尾结点（头结点方便访问链表，尾结点方便插入），直至这个链表访问完就可以结束了，最后一步就是将两个链表连起来，这个分
public ListNode partition(ListNode head, int x) {// write code hereListNode cur = head;ListNode beforeStart = null;ListNode beforeEnd = null;ListNode afterStart = null;ListNode afterEnd = null;while (cur !=null){if (cur.val < x){if (beforeStart == null){beforeStart = cur;beforeEnd = beforeStart;}else{beforeEnd.next = cur;beforeEnd = beforeEnd.next;}}else{if (afterStart == null){afterStart = cur;afterEnd = cur;}else{afterEnd.next = cur;afterEnd = afterEnd.next;}}cur = cur.next;}if (beforeStart == null){return afterStart;}beforeEnd.next = afterStart;if (afterStart != null){afterEnd.next = null;}return beforeStart;
}第七题：链表的回文结构。
链表的回文结构_牛客题霸_牛客网
观察是否是回文可以转换成反转中间结点后的链表，可以通过对比前后数据判断是否是回文。
（1）.首先先找中间结点
（2）.其次是反转后半部分的链表
（3）.最后对比前后结点的数据是否相同，或者可能出现前结点的下一个结点是尾结点。
public boolean chkPalindrome(ListNode head) {// write code hereListNode fast = head;ListNode slow = head;//找中间结点while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}ListNode ret = slow.next;while (ret != null){ListNode cur = ret.next;ret.next = slow;slow = ret;ret = cur;}while (head != slow){if (head.val != slow.val){return false;}if (head.next == slow && head.val == slow.val){return true;}head = head.next;slow = slow.next;}return true;
}第八题：输入两个链表，找出它们的第一个公共结点。
160. 相交链表 - 力扣（LeetCode）
找两个链表的公共结点，首先这个链表一定是一个往左倒着的Y，不能是往右倒着的，也不能是倒着的X（一个单链表连接着一个next域，可以两个链表的next域指向同一个，但不能一个链表的next域指向两个链表），重点是长的链表需要先走差值步，
（1）.首先先找到连个链表的差值是多少；（把长链表放在pL上）
（2）.然后让长的链表先走差值步；（pL走差值步）
（3）.然后两个链表一起走，走到两个结点相同时结束，然后就返回公共结点。
public int length(ListNode head){int count = 0;while(head != null){count++;head = head.next;}return count;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//计算链表长度int lenA = length(headA);int lenB = length(headB);//修正ListNode pL = headA;ListNode pS = headB;int len = lenA - lenB;if (len < 0){pL = headB;pS = headA;len = lenB - lenA;}//最长的链表先走差值个while(len > 0){pL = pL.next;len--;}//再一起走到相遇点while (pL != pS){pL = pL.next;pS = pS.next;}return pL;
}第九题：给定一个链表，判断链表中是否有环。
141. 环形链表 - 力扣（LeetCode）
判断是否有环重点是设置两个快慢结点，如果存在环，那么这两个结点一定会相遇。
public boolean hasCycle(ListNode head) {if (head == null)return false;ListNode fast = head;ListNode show = head;while (fast != null && fast.next != null){fast = fast.next.next;show = show.next;if (fast == show){return true;}}return false;
}第十题：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
142. 环形链表 II - 力扣（LeetCode）
这个题建立在是否有环的基础上，如果有环，那么快慢结点就会相遇，相遇的结点和头结点到环的第一个的步数是一样的，所以当这两个结点相同时就是环的第一个节点了。
（1）. 链表如果是空，返回null；
（2）. 判断是否有环，没有返回null，有则跳出循环；
（3）. 相遇的结点和头结点一起走，当它们相同时停止，并返回该结点。
public ListNode detectCycle(ListNode head) {if (head == null){return null;}ListNode fast = head;ListNode slow = head;while (true){if (fast == null || fast.next == null){return null;}fast = fast.next.next;slow = slow.next;if (fast == slow){break;}}int count = 0;while (fast != head){fast = fast.next;head = head.next;count++;}return head;
}