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

力扣

思路1：虚拟头节点。

????????1、对相邻的节点进行两两交换，首先添加虚拟头节点更好方便处理节点。head指向遍历节点，prev指向遍历节点的前置节点。

        ListNode dummyNode = new ListNode(0);//虚拟头节点
        dummyNode.next = head;
        ListNode prev = dummyNode;

? ? ? ? 2、循环条件很简单，判断至少有两个节点，才好交换。while（prev.next != null && prev.next.next != null ）。

? ? ? ? 3、进行交换，首先得保存后继节点吧，所以 ListNode temp = head.next.next; // 缓存 next?

? ? ? ? 4、然后交换1 2节点，prev.next = head.next; // 将 prev 的 next 改为 head 的 next

????????????????????????head.next.next = head; // 将 head.next(prev.next) 的next，指向 head?

????????5、2号节点的后继应该是1的后继，head.next = temp;// 将head 的 next 接上缓存的temp 。

? ? ? ? 6、交换1 2 完成，接下来要交换3 4，temp应该指向5，head指向3，prev指向2。

????????????????prev = head; // 步进1位

????????????????head = temp; // 步进1位

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(0);//虚拟头节点
        dummyNode.next = head;
        ListNode prev = dummyNode;
        while (prev.next != null && prev.next.next != null) {
            ListNode temp = head.next.next; // 缓存 next
            prev.next = head.next; // 将 prev 的 next 改为 head 的 next
            head.next.next = head;  // 将 head.next(prev.next) 的next，指向 head
            head.next = temp;// 将head 的 next 接上缓存的temp
            prev = head;    // 步进1位
            head = temp;    // 步进1位
        }
        return dummyNode.next;
    }
}

?思路2: 递归，使用递归三部曲。

找终止条件：本题终止条件很明显，当递归到链表为空或者链表只剩一个元素的时候，没得交换了，自然就终止了。
找返回值：返回给上一层递归的值应该是已经交换完成后的子链表。
单次的过程：因为递归是重复做一样的事情，所以从宏观上考虑，只用考虑某一步是怎么完成的。我们假设待交换的俩节点分别为head和next，next的应该接受上一级返回的子链表(参考第2步)。就相当于是一个含三个节点的链表交换前两个节点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}

递归可以参考一下大佬写的一个博客，附有详细的图文介绍：三道题套路解决递归问题 | lyl's blog

二、19.删除链表的倒数第N个节点

力扣

????????思路：此题难度一般，倒数第n个，使用快慢指针让快指针先走n个节点，然后再一起遍历，最后慢指针就是倒数第n个节点，删除节点顺便定义前置节点。结束了

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while(n-- > 0) {
            fast = fast.next;
        }
        ListNode prev = dummy;
        while(fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        prev.next = slow.next;
        slow.next = null;
        return dummy.next;
    }
}

三、面试题 02.07. 链表相交

力扣

思路：同样可以使用双指针，分别统计A B链表的长度，让较长链表先走链表之差个节点，然后再一起遍历，就可以找到相交节点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        int lenA = 0;
        int lenB = 0;
        int diff = 0;
        while (pA != null) {
            lenA++;
            pA = pA.next;
        }
        while (pB != null) {
            lenB++;
            pB = pB.next;
        }
        pA = headA;
        pB = headB;
        if (lenA > lenB) {
            diff = lenA - lenB;
            while (diff-- > 0) {
                pA = pA.next;
            }
        }else {
            diff = lenB - lenA;
            while (diff-- > 0) {
                pB = pB.next;
            }
        }
        while (pA != null && pB != null) {
            if (pA == pB) {
                return pA;
            }else {
                pA = pA.next;
                pB = pB.next;
            }
        }
        return null;
    }
}

四、142.环形链表II?

力扣

思路1：使用快慢指针找是否存在环比较容易，这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合，难点在于如何找到环的入口。

????????假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。如图所示：

?????????那么相遇时： slow指针走过的节点数为:?x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。

????????将x单独放在左面：x = n (y + z) - y?，

????????再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z?注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。? ? ?

????????当 n为1的时候，公式就化解为?x = z，

????????这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && slow != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode res = head;
                while (res != slow) {
                    res = res.next;
                    slow = slow.next;
                }
                return res;
            }
        }
        return null;
    }
}

思路2: 有环肯定是后续节点指向了前面的节点了，使用set集合来判断是否有环。（Set注重独一无二的性质,该集合可以知道某物是否已经存在于集合中,不会存储重复的元素）

? ? ? ? 使用不会重复这个特性，遍历链表依次将节点存入Set集合中，? 如果遍历重复节点则表示有环。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode cur = head;    //用来遍历链表
        while (set.add(cur) != false) {
            if (cur == null) return null;
            cur = cur.next;
        }
        return cur;
    }
}

? ? 这里顺便复习一下Java的各种集合，链接如：Java集合详解