代码随想录算法训练营第4天｜链表Part02

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

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

注意递归版本代码，面试可能让再撕。

• 迭代法

• 递归法

var swapPairs = function (head) {
    let dummy = new ListNode(null, head);
    if (!head || !head.next) return head;
    let pre = dummy, cur, next;
    while (pre.next && pre.next.next) {
        cur = pre.next, next = pre.next.next;
        cur.next = next.next;
        next.next = cur;
        pre.next = next;
        pre = cur;
    }
    return dummy.next;
};

var swapPairs = function (head) {
    if (!head || !head.next) return head;
    let cur = head, next = head.next;
    head.next = next.next;
    next.next = cur;
    cur.next = swapPairs(cur.next);
    return next;
};

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

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

• 哨兵节点可以消除特判逻辑。
• 可以借助 n = 1 时的情况辅助思考。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。

LeetCode142. 环形链表 II

A = (n - 1) (B + C) + C 意味着只要从碰撞点和起点以同样的速度扫描，下次碰撞点一定是环的入口节点。