跟着卡哥学算法Day 4：链表中等题目
24. 两两交换链表中的节点 🌟🌟
题目描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路
虚拟头节点
const head = new ListNode(0, head)-
什么时候遍历结束
// 奇数节点 cur.next.next = null// 偶数节点 cur.next = nullcur.next !== null && cur.next.next !== null -
两两交换节点即可
每次 1 和 3 都会断掉，所以需要提前保存下来
// 节点1let temp = cur.next// 节点3let temp1 = cur.next.next.nextcur.next = cur.next.nextcur.next.next = temptemp.next = temp1// 移动cur = cur.next.next
代码
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {ListNode} */var swapPairs = function (head) { const data = new ListNode(0, head) let cur = data while (cur.next && cur.next.next) { // 节点1 let temp = cur.next // 节点3 let temp1 = cur.next.next.next
cur.next = cur.next.next cur.next.next = temp temp.next = temp1 cur = cur.next.next } return data.next}19.删除链表的倒数第 N 个节点 🌟🌟
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
输入：head = [1], n = 1 输出：[]
输入：head = [1,2], n = 1 输出：[1]思路
重点
- 快慢指针：快指针移动 n+1 步，快慢指针同时移动
- 快指针指向链表末尾，慢指针刚好指向删除节点的前一个节点插入，必须知道前一个节点，即第 n 个节点一定是 curNode.next
代码
var removeNthFromEnd = function (head, n) { let data = new ListNode(0, head) let fast = data let slow = data
while (n) { fast = fast.next n-- } while (fast.next !== null) { fast = fast.next slow = slow.next } slow.next = slow.next.next
return data.next}面试题 02.07. 链表相交 🌟
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路
两个单链表从交点开始，后面的节点都指向同一个节点。
如：
链表 A：4 → 1 → 8 → 4 → 5链表 B：5 → 6 → 1 → 8 → 4 → 5从节点 8 开始，后面的节点都指向同一个节点。
- 获取两个链表的长度（遍历），将长链表放在前面，短链表放在后面
- 求长度差，将长链表指针向后移动长度差位，直到两个链表指针相等
- 遍历两个链表，如果两个链表节点相等，则返回该节点
代码
var getLength = function (head) { let size = 0, cur = head while (cur) { size++ cur = cur.next } return size}var getIntersectionNode = function (headA, headB) { let curA = headA, curB = headB
let lenA = getLength(headA) let lenB = getLength(headB)
if (lenA < lenB) { ;[curA, curB] = [curB, curA] ;[lenA, lenB] = [lenB, lenA] }
let i = lenA - lenB while (i-- > 0) { curA = curA.next } while (curA && curA !== curB) { curA = curA.next curB = curB.next } return curA}142.环形链表 II 🌟🌟
题目描述
题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
思路
判断链表是否有环
快慢指针，快指针移动两个节点，慢指针移动一个节点，如果最终都指向 null，则说明没有环；如果快慢指针相遇，说明链表一定有环
head = [3,2,0,-4], pos = 1这里 pos = 1 代表索引 1 处的节点（值为 2）是环的入口节点，表示 -4 指向 2，形成环。返回索引为 1 的节点
如何找到环的入口
变量定义
- x：从链表头到环入口的距离（节点数）。
- y：从环入口到快慢指针相遇点的距离。
- z：从相遇点走到环入口的剩余距离（也就是环的长度减去 y）。
快慢指针相遇时的关系：
- slow 指针 走了
x + y步。 - fast 指针 走了
x + y + n(y + z)步，其中n为快指针在环中转过的圈数，（至少 n = 1）
因为 fast 指针移动速度是 slow 指针的两倍，所以
2(x + y) = x + y + n(y + z)两边消掉 x + y，得到
x + y = n (y + z)求环形入口，即头节点到环形入口节点的距离x，得到
x = n(y + z) - yx = (n - 1)(y + z) + z此时，如果 n = 1，即快指针 fast 转一圈就遇到了慢指针 slow，简化为 x = z，即从头节点和相遇节点同时出发一个指针，每次只走一个节点，那么相遇节点就是环形入口节点。
当 n 大于 1 时，即相遇节点的指针在圈内转了n圈后，在环形节点入口遇到了从头节点出发的指针
时间复杂度: O(n)，快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于 2n
代码
var detectCycle = function(head) { if(!head || !head.next) return null; let slow = head.next, fast = head.next.next; while(fast && fast.next && fast!== slow) { slow = slow.next; fast = fast.next.next; } if(!fast || !fast.next ) return null; slow = head; while (fast !== slow) { slow = slow.next; fast = fast.next; } return slow;};