代码随想录算法训练营Day04: 24.两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表||

24. 两两交换链表中的节点

tag： #链表 #反转
leetcode 地址：24. 两两交换链表中的节点

代码：

function swapPairs(head: ListNode | null): ListNode | null {
    const resHead = new ListNode()
    resHead.next = head
    let tem = resHead
    while(tem.next && tem.next.next) {
        const node1 = tem.next
        const node2 = tem.next.next
        node1.next = node2.next
        node2.next = node1
        tem.next = node2
        tem = node1
    }
    return resHead.next
};

思路解析：

• 相比于92. 反转链表 II这个更加简单一些，因为只是两两相邻的交换，因此可以直接手动交换位置

19. 删除链表的倒数第 N 个结点

tag： #链表 #双指针 #虚拟头节点
leetcode 地址：19. 删除链表的倒数第 N 个结点

代码：

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
	if(head == null) return null
	
    let newHead = new ListNode()
    newHead.next = head
    let left = newHead, right = newHead

    while(n--) {
        right = right.next
    }
    while(right.next) {
        right = right.next
        left = left.next
    }
    left.next = left.next.next

    return newHead.next
};

面试题 02.07. 链表相交

tag： #链表 #双指针 #总长度相等
leetcode 地址：面试题 02.07. 链表相交

代码：

var getIntersectionNode = function(headA, headB) {
    let p1 = headA, p2 = headB
    while(p1 !== p2) {
	    // 注意这里要用 p1、p2 作为判断条件
	    // 如果用 p1.next 作为判断条件，那么当 headA、headB 不相交的时候
	    // p1、p2 不会同时等于 null，因此会造成死循环
        p1 = p1 ? p1.next : headB
        p2 = p2 ? p2.next : headA
    }

    return p1
};

142. 环形链表 II

tag： #链表 #环形 #数学 #双指针
leetcode 地址：142. 环形链表 II

代码：

function detectCycle(head: ListNode | null): ListNode | null {
    let slowNode: ListNode | null = head,
        fastNode: ListNode | null = head;
    while (fastNode !== null && fastNode.next !== null) {
        slowNode = slowNode!.next;
        fastNode = fastNode.next.next;
        if (slowNode === fastNode) {
            slowNode = head;
            while (slowNode !== fastNode) {
                slowNode = slowNode!.next;
                fastNode = fastNode!.next;
            }
            return slowNode;
        }
    }
    return null;
};

思路解析：
分为 x，y，z 的距离
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

(x + y) * 2 = x + y + n (y + z)

即：x + y = n (y + z)，x = n (y + z) - y
当 n = 1， x = z
当 n = 2， x = y + z + z

因此当 fast 和 slow 两个指针相遇的时候，我们从 head 新移动一个指针和 slow 一起移动，相遇点既是入口

相似题目：