24.交换链表结点
题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）
文章链接：代码随想录 (programmercarl.com)
视频链接：代码随想录算法公开课 | 最强算法公开课 | 代码随想录
第一想法
正常模拟，先画图再说，有点像链表反转？这个模拟完全是错误的，交换第二对时会把第一对的末指针丢掉。
代码随想录想法
有三个比较重要关注的点：
cur的定义一定是要预备交换的一对结点的前一个结点，也就是已经交换完结的一对结点之中的第二个结点。这是理解我们为什么要引入虚拟节点，和循环条件的关键。
交换过程中，每一句代码执行时，哪里指针断了，哪里指针脸上得画图看清楚。不要弄丢前后指针。
while (cur.next!=null&&cur.next.next!=null)这个循环条件要注意前后关系，否则会空指针异常
代码
class Solution2{
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(-1, head);
ListNode cur = dummyNode;
while (cur.next!=null&&cur.next.next!=null){
ListNode temp1 = cur.next;
ListNode temp2 = cur.next.next.next;
cur.next = cur.next.next;
cur.next.next = temp1;
temp1.next = temp2;
cur = cur.next.next;
}
return dummyNode.next;
}
}19.删除链表的倒数第N个结点
题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
文档链接：代码随想录 (programmercarl.com)
视频链接：链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点_哔哩哔哩_bilibili
第一想法
暴力解题法，第一遍遍历链表
第二遍指针初始时，链表到达尾部，往回遍历，当i = n+1时，指针恰好等于要删除结点的前一个结点，删除结点。
为方便删除应当设置链表的虚拟头结点。
暴力写不出来，方法二：
首先设置虚拟头结点，然后设置距离为n+1的双指针。
代码随想录想法
双指针想法一致,算是靠自己写的吧。
问题
相隔n个单位，所以快指针要跳n+1个单位，循环是（for int i =0;i<=n;i++)，左闭右闭循环n+1次，左闭右开，循环n次。
代码
class Solution1 {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyNode = new ListNode(-1,head);
ListNode begin = dummyNode;
ListNode end =dummyNode;
for (int i = 0; i <= n; i++) {
end = end.next;
}
while(end!=null){
begin =begin.next;
end = end.next;
}
begin.next = begin.next.next;
return dummyNode.next;
}
}面试题02.07题链表相交
题目链接：面试题 02.07. 链表相交 - 力扣（LeetCode）
文档链接：代码随想录 (programmercarl.com)
第一想法
和19题很类似，同样是长度差。
先统计链表A和链表B的长度，设置相距链表长度差的双指针，二者同时往后走。一旦数值相等，那么就一定是相同的第一个结点。
代码
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode longList = headA;
ListNode shortList = headB;
int longLength = 0;
int shortLength = 0;
while (longList!=null){
longLength++;
longList = longList.next;
}
while (shortList!=null){
shortLength++;
shortList = shortList.next;
}
longList = headA;
shortList = headB;
if(longLength<shortLength){
ListNode tempNode = longList;
longList = shortList;
shortList = tempNode;
int temp = longLength;
longLength = shortLength;
shortLength = temp;
}
int gap = longLength-shortLength;
while(gap-->0)
longList = longList.next;
while (longList!=null){
if(longList ==shortList )
return longList;
longList = longList.next;
shortList = shortList.next;
}
return null;
}
}142.环形链表2
第一想法：
第一想法就是我做不出来
代码随想录思路：
慢指针一次走一个结点，快指针一次走两个结点，快指针相对慢指针一个结点一个结点的追赶，所以总会有一次相遇。
假设快指针和慢指针相遇，其中慢指针一定会在尚未走完的第一圈，而快指针可能已经转了好几圈。
当相遇时，慢指针走的距离：x+y
快指针走的距离：x+n(y+z)+y
有等式:2（x+y) = x+n(y+z)+y
即：x = (n-1)(y+z)+z;
n至少是>=1的
当n = 1 时，只需要设置起始点指针和相遇点指针同时往前走，相等时即是程序入口，因为x = z
当n>1时，只不过相遇处的指针在圆里多转几圈，将圆展开来还是一样的。
while (fast !=null && fast.next != null){
fast = fast.next.next;
slow =slow.next;
}这个判断条件要会想起24题的判断条件，走两步的指针如何在判断终点的同时避免空指针异常。
代码：
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast !=null && fast.next != null){
fast = fast.next.next;
slow =slow.next;
if(slow==fast){//如果有环
ListNode index1 = head;
ListNode index2 = slow;
while (index1!=index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
