相交链表 && 删除链表的倒数第 N 个结点 && 两两交换链表中的节点

相交链表

这是力扣 160 题

给你两个单链表的头节点  headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据  保证  整个链式结构中不存在环。 注意，函数返回结果后，链表必须  保持其原始结构 。

解题思路

这道题目并不是很难，但是我们要弄清楚这里相交的交点。我们需要注意，这里相交是指指针相等，而不是数值相等。我第一次做这题的时候，就误以为是数值相等，就这样稀里糊涂地做起来了，结果可想而知，未通过。弄清楚了这个，接下来就用我们的老朋友 — 双指针，来介绍一下这题的思路。

双指针解法

创建两个指针 a 和 b，分别指向 headA、headB，然后当 a 与 b 不相等时，先遍历各自节点部分。如果存在公共部分，再遍历公共部分，接着遍历非公共部分，直到 a 等于 b，则找到 a 为相交点。否则遍历完各自节点均为有公共部分，说明不相交。用大白话来表示就是：把它当成两个人赛跑，速度相同，最后终点也相同。若有相遇（相交）的情况，说明最后到终点的一段路程也相同。如不相遇（相交），则最后同时到达终点。每一步操作都需要同时更新 a 和 b 两个指针。

• a 与 b 不相等，一起移动，遍历完自己的链表后再去遍历对方的链表。

这道题不难，但是需要理解，理解这个相交的情况，理解如何处理相交。动手多画，你就会有所收获。

相关代码如下：

var getIntersectionNode = function(headA, headB) {
    let a = headA, b = headB;
    while(a !== b) {
        a = a ? a.next : headB;
        b = b ? b.next : headA;
    }
    return a;
};

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

这是力扣 19 题

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

解题思路

这又是一道中等难度的题，但是其实并不是特别难，因为这是一道有关双指针的经典应用。双指针在数组那块已经讲过很多次了，这是第一次运用到链表上。在这道题目上，可以将双指针的作用发挥到淋漓尽致，因此通过这道题目可以更好地帮助大家理解双指针解法以及这种解法在链表上的应用。

双指针解法

这道题目里双指针又可以称为快慢指针，定义 slow 和 fast 两个指针来移动（在下面代码中，我用 n1 和 n2 来表示 slow 和 fast 两个指针）。

除了两个指针之外，这里又需要使用到虚拟头节点，使用虚拟头节点的好处就不用我多说了，它方便处理删除实际头节点的逻辑。我们让定义好的两个指针初始值为虚拟头节点。如果要删除倒数第 N 个节点，首先让 fast 指针移动 N 步，然后让 fast 指针和 slow 指针同时移动，直到 fast 指针指向链表末尾。删掉 slow 指针所指向的节点就可以了。

• fast 和 slow 同时移动，直到 fast 指向 null

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

• 通过 slow 删除 slow->next 的节点。

slow.next = slow.next.next;

这就是整个过程的大体思路了，建议可以在纸上多画画，多模拟几遍操作，就能想得更清楚了。链表的题目如果能在纸上通过不断模拟想清楚，就能简单很多。根据以上步骤就能轻易写出代码。

相关代码如下：

// n1和n2代表快慢指针

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode();
    dummy.next = head;
    let n1 = dummy;
    let n2 = dummy;
    for(let i=0;i<=n;i++){
        n2 = n2.next;
    }
    while(n2!==null){
        n1 = n1.next;
        n2 = n2.next;
    }
    n1.next = n1.next.next;
    return dummy.next;
};

两两交换链表中的节点

这是力扣 24 题

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

解题思路

这是一道中等难度的题目，是有一点点难度的。对于链表类的题目，我的建议是动手画图，将链表画出来，然后根据题目要求来模拟链表的一系列操作。对于这道题而言，画图能够清晰地模拟出思路

题目要求的是交换相邻的两个节点，并且要求不修改节点内的值，因此如上面画出的图所示。current 是创建的头节点。在链表的题目中，创建虚拟头节点对解题十分方便，这里让 current 指向虚拟头节点。

解题思路如下：

• 首先定义一个虚拟头节点 dumy
• 然后用 current 来代表头节点，并让 current 指向虚拟头节点，current -> n1 -> n2 需要被转换成 current -> n2 -> n1
• 其次 current 指向 n1，然后再去反转 n1 之后的节点
• 最后返回创建的虚拟头节点的 next

相关代码如下：

var swapPairs = function(head) {
    let dummy = new ListNode();
    dummy.next = head;
    let current = dummy;
    while(current.next!==null&&current.next.next!==null){
        let n1 = current.next;
        let n2 = current.next.next;
        current.next = n2;
        n1.next = n2.next;
        n2.next = n1;
        current = n1;
    }
    return dummy.next;
};

光看代码可能会有些难以完全理解，建议大家可以动手画图去模拟这些交换、移动的与指针相关的操作，否则在不画图的情况下仅仅靠去想这些指针的操作，会很容易打乱顺序。这道题难度属于中等，略微会有一点点难度，所以可以多看看它并理解它。理解这道题也可以帮助大家更好地理解链表。