代码随想录算法训练营--打卡day3

复习：标注感叹号的需要在电脑上重新做几遍 

 一.两两交换链表中的节点！！

1.题目链接 

24. 两两交换链表中的节点 - 力扣（LeetCode）

2.思路

画图

3.代码

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy=new ListNode(0);dummy.next=head;ListNode cur=dummy;while(cur.next!=null&&cur.next.next!=null){ListNode tmp1=cur.next;ListNode tmp2=cur.next.next.next;cur.next=cur.next.next;cur.next.next=tmp1;tmp1.next=tmp2;cur=cur.next.next;}return dummy.next;}
}

二.删除链表中的倒数第N个节点

1.题目链接

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

2.思路

通过虚拟头结点（处理头结点本身需要删除的情况）+快慢指针差N步（精准定位待删节点的前驱）

3.代码

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy=new ListNode(0);dummy.next=head;ListNode slow=dummy;ListNode fast=dummy;while(n>0){fast=fast.next;n--;}while(fast.next!=null){slow=slow.next;fast=fast.next;}slow.next=slow.next.next;return dummy.next;}
}

 三.链表相交

1.题目链接

面试题 02.07. 链表相交 - 力扣（LeetCode）

2.注意点！！

  p=p==null?headB:p.next;
  q=q==null?headA:q.next;

3.代码

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p=headA;ListNode q=headB;while(p!=q){p=p==null?headB:p.next;q=q==null?headA:q.next;}return p;}
}

四.环形链表！！

1.题目链接

142. 环形链表 II - 力扣（LeetCode）

2.易错点

while()循环条件

3.代码

public 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 (fast == slow) {// 让一个指针从头节点开始，另一个指针从相遇点开始while (head != fast) {// 头指针和相遇点指针同时移动一步head = head.next;fast = fast.next;}// 当它们再次相遇时，相遇点就是环的起始节点return head;}}// 如果循环结束都没有相遇，说明链表中不存在环，返回 nullreturn null;}
}