【12.28】转行小白历险记-刷算法04

01两两交换链表中的节点

整体思路?

1.要修改后一个节点的指向一定要知道前一个节点的指向才可以改变后面一个节点的

2.分情况奇数和偶数节点，终止条件很重要

3.虚拟头节点，是对我们操作的指针是不是头节点进行判断

02删除链表的倒数第N个节点

思路

1.双指针法，快指针先移动n步，然后慢指针移动，当两个相等的时候说明

代码逻辑

1. 初始化：

   let ret = new ListNode(0, head), slow = fast = ret;

   ret 是一个新创建的虚拟头节点，其 next 指向链表的实际头节点 head。这样做是为了简化头节点删除的边界情况处理。

   • slow 和 fast 是两个指针，初始时都指向这个虚拟头节点。

2. 移动 fast 指针：

   while(n--) fast = fast.next;

   fast 指针先向前移动 n 步。这样做是为了创建一个 fast 和 slow 之间有 n 个节点的间隔。

3. 同时移动 fast 和 slow 指针：

   while (fast.next !== null) 
   { fast = fast.next; slow = slow.next; }

   • 然后同时移动 fast 和 slow 指针，直到 fast 指针指向最后一个节点。此时，slow 指针将指向需要删除节点的前一个节点。

4. 删除节点：

   slow.next = slow.next.next;

   修改 slow.next，使其跳过下一个节点（即要删除的节点），直接指向下下一个节点。

5. 返回修改后的链表头节点：

   return ret.next;

   由于 ret 是虚拟头节点，其 next 指向原链表的头节点或新的头节点（如果头节点被删除）。因此，返回 ret.next 就是返回删除指定节点后的链表头节点。

总结

这个函数利用快慢指针技巧来定位并删除链表中倒数第 n 个节点。使用虚拟头节点简化了对头节点的特殊处理，使得算法能够统一处理所有情况。

03环形链表

代码逻辑

1. 初始化：

   if (!head || !head.next) return null;
   let slow = head.next, fast = head.next.next;

   首先检查链表是否至少有两个节点（否则环不可能存在）。然后初始化两个指针：slow 每次向前移动一个节点，fast 每次向前移动两个节点。

2. 检测环：

   while (fast && fast.next && fast !== slow)
   { slow = slow.next; fast = fast.next.next; }

   这个循环继续执行直到 fast 和 slow 相遇，或者 fast 到达链表末尾（这意味着链表中没有环）。如果 fast 和 slow 相遇，说明链表中存在环。

3. 确定环的入口：

   if (!fast || !fast.next) return null; 
   slow = head; 
   while (fast !== slow) 
   { slow = slow.next; fast = fast.next; }

   如果链表中存在环，将 slow 重置到头节点，然后 slow 和 fast 同时每次向前移动一个节点，直到它们再次相遇。它们相遇的节点就是环的入口。

4. 返回环的入口节点：

   return slow;

   返回找到的环的入口节点。