阅读量:0
移除链表元素
题目连接：
https://leetcode.cn/problems/remove-linked-list-elements/description/
使用双指针法，开始时，一个指针指向头节点，另一个指针指向头节点的下一个结点，然后开始遍历链表删除结点。
这里要注意如果是空链表的话，使用双指针第二个指针会发生空指针异常，所以要判断一下
最后程序运行到最后，我们还差头节点没有判断，最后加上即可。
class Solution { public ListNode removeElements(ListNode head, int val) { if(head == null) { return head; } ListNode prev = head; ListNode cur = head.next; while(cur != null) { if(cur.val == val) { prev.next = cur.next; } else { prev = cur; } cur = cur.next; } if(head.val == val) { head = head.next; } return head; } } 反转链表
题目连接：
https://leetcode.cn/problems/reverse-linked-list/description/
我们还是使用双指针，不过这次有一个指针就是头指针，因为反转链表之后的头指针会发生改变，那还不如直接让头指针一起移动，先将另一个指针指向头指针的下一个结点，然后开始遍历链表，把每一个结点的指针指向的对象变为前面的对象。
class Solution { public ListNode reverseList(ListNode head) { if(head == null) { return head; } ListNode cur = head.next; head.next = null; while(cur != null) { ListNode tmp = cur.next; cur.next = head; head = cur; cur = tmp; } return head; } } 链表的中间结点
题目链接：
https://leetcode.cn/problems/middle-of-the-linked-list/description/
使用快慢指针，快指针每次走两步，慢指针每次走一步，最后慢指针所指向的结点就是 中间结点
原理：fast = 2slow = 总路程
这里要注意循环的结束条件：
当fast== null 并且 fast.next == null时，才能进入循环，并且 fast==null,要放在前面，因为只用fast不是null时才能进行 fast.next 的判断
class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } } 返回倒数第 k 个节点
题目链接：
https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
还是使用快慢指针，先让快指针走 k-1 步，然后慢指针和快指针一起走，每次走一步，最后快指针走到最后一个结点时，慢指针所指向的节点就是倒数第 k 个节点。
原理就是让slow和fast的差值j就是k
class Solution { public int kthToLast(ListNode head, int k) { ListNode fast = head; ListNode slow = head; for(int i=0; i<k-1; i++) { fast = fast.next; } while(fast.next != null) { slow = slow.next; fast = fast.next; } return slow.val; } } 合并两个有序的链表
题目链接：
https://leetcode.cn/problems/merge-two-sorted-lists/description/
创建一个新的头节点，list1和list2开始遍历各自的链表，然后比较，插入到新链表中，最后再看一下哪些链表没有遍历完，然后把没有遍历完的链表直接插入即可。
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null) { return list2; } if(list2 == null) { return list1; } ListNode newHead = new ListNode(); 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; } if(list1 != null) { cur.next = list1; } if(list2 != null) { cur.next = list2; } return newHead.next; } } 分割链表
我们可以将单链表拆成两个链表，一个链表存储小于x 的结点，另一个链表存储大于等于x 的结点，然后将两个链表合并
这里建议使用带头链表，也就是我们常说的带哨兵位的链表，这个链表最大的好处就是可以避免头插的复杂情况，既然使用了哨兵位，就要知道最后哨兵位是要被丢弃的。
public class Partition { public ListNode partition(ListNode pHead, int x) { ListNode headA = new ListNode(-1); ListNode aLast = headA; ListNode headB = new ListNode(-1); ListNode bLast = headB; ListNode cur = pHead; while(cur != null) { if(cur.val < x) { aLast.next = cur; aLast = aLast.next; } else { bLast.next = cur; bLast = bLast.next; } cur = cur.next; } aLast.next = headB.next; bLast.next = null; return headA.next; } } 链表的回文结构
解题思路：
我们可以使用快慢指针来遍历链表找到中间结点，然后就可以把后半部分的链表进行反转，之后从这个链表头尾结点开始向中间遍历。
易错点：
1.链表的结点个数有奇数和偶数两种类型，我们需要分别讨论
2.区分奇数个结点还是偶数个结点可以从一开始找完中间结点的时候，从fast入手,因为找中间结点的循环结束就是fast最后指向尾节点还是null。
3.要一定要保存好fast的信息，因为后面在反转链表的时候fast其实已经发生了改变。
public class PalindromeList { public boolean chkPalindrome(ListNode A) { //如果是空链表返回true if(A == null) { return true; } ListNode slow = A; ListNode fast = A; //找到中间结点 while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } //保存fast的结点信息，避免后面反转链表丢失信息 boolean isOdd = true;//是否是奇数个结点 if(fast == null) { isOdd = false; } //反转后半部分的链表 ListNode prev = slow; ListNode cur = slow.next; while(cur != null) { ListNode curN = cur.next; cur.next = prev; prev = cur; cur = curN; } //前后遍历链表 ListNode pA = A; ListNode last = prev; //偶数个结点 if(!isOdd) { while(pA.next != last) { if(pA.val != last.val) { return false; } pA = pA.next; last = last.next; } if(pA.val != last.val) { return false; } } if (isOdd) { //奇数个结点 while(pA != last) { if(pA.val != last.val) { return false; } pA = pA.next; last = last.next; } } return true; } } 相交链表
题目链接：
https://leetcode.cn/problems/intersection-of-two-linked-lists/
由于是相交链表，在公共结点之前两个链表可能有一个差值，如果我们能找到这个差值，让长的链表先走差值不属，然后两个链表一起遍历，直到相遇到公共结点。
这个差值就是两个链表的长度的差。
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = 0; int lenB = 0; ListNode cur = headA; while(cur != null) { lenA++; cur = cur.next; } cur = headB; while(cur != null) { lenB++; cur = cur.next; } int k = 0; ListNode pl = null; ListNode ps = null; if(lenA > lenB) { k = lenA - lenB; pl = headA; ps = headB; } else { k = lenB - lenA; pl = headB; ps = headA; } while(k != 0) { pl = pl.next; k--; } while(pl != ps) { pl = pl.next; ps = ps.next; } return pl; } } 环形链表
题目链接：
https://leetcode.cn/problems/linked-list-cycle/
这里使用快慢指针，快指针一次走两步，慢指针一次走一步，当快指针运动到fast == null 或者 fast .next == null 这个条件时，说明链表不存在环，如果有链表存在环，那么快指针就会先进入到环中一直做圆周运动，一定会存在某一个时刻快慢指针会相遇，这时候返回true即可。
public class Solution { public boolean hasCycle(ListNode head) { 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; } } 为什么快指针每次走两步，慢指针走一步可以？
快指针会率先进入环中，然后慢指针后晚一点进入环中，由于两个指针的速度是每次差一步，也就是说两个指针每运动一次，二者之间的距离就会缩短1步，最后两个指针一定会相遇。
快指针一次走3步，走4步，…n步行吗？
快指针如果每次走三步，假设两个指针的位置如下：
那二者永远都不会相遇
其他情况由读者自行探讨~~
环形链表Ⅱ （找入口点）
题目链接：
https://leetcode.cn/problems/linked-list-cycle-ii/description/
我们还是使用快慢指针来做。
假设起点与入口点的距离为 x ，环的周长为 C ，慢指针与快指针相遇点离起点的距离为L ：
慢指针所走的路程为 x + L
快指针所走的路程为 x + L + nC (n为正整数，n = 1,2,3,4…)
这里解释一下两者的路程计算问题：
在慢指针还没有进入口点的时候，就已经至少路过一次相遇点，所以当慢指针刚刚进入环中的时候，快指针最少已经走了一圈，最多走了 n 圈。
因为慢指针刚进入环中的时候，快指针和它最多相差一个圈的距离，并且快指针的速度比慢指针的速度要快，所以慢指针是不可能走完一圈的（假设慢指针走完一圈，那快指针一定走完一圈再多一点，所以慢指针在完成一圈之前一定会被追上），所以慢指针所走的路程为 x + L，快指针所走的路程为 x + L + nC (n为正整数，n = 1,2,3,4…)中的 nC 是遇到慢指针之前就已经完成好的
当快慢指针在环中相遇时，由于快指针的速度是慢指针的速度的两倍，所以慢指针的路程是快指针的一半，即 2 * (x + L) = x + L + nC，化简整理得 x + L = nC 即 x = nC - L
推导结论：
让一个指针从头开始遍历，另一个指针从相遇点开始遍历，两个指针每次走一步，一定会在入口点相遇。
public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(slow == fast) { break; } } //没有环 if(fast == null || fast.next == null) { return null; } ListNode meet = fast; ListNode str = head; while(meet != str) { meet = meet.next; str = str.next; } return str; } } 