两两交换链表中的节点

难点在于，要用到临时变量记录被交换位置的节点，边界的处理，以及cur的移动

public ListNode swapPairs(ListNode head) {
        //定义哨兵节点
        ListNode s = new ListNode(0, head);
        //定义当前指针位置
        ListNode cur = s;
        //临时变量记录要被交换的节点
        ListNode temp1;
        //临时变量记录cur要移动的位置
        ListNode temp2;
        //定义循环边界
        while(cur.next != null && cur.next.next != null){
            temp1 = cur.next;
            temp2 = cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = temp1;
            temp1.next = temp2;
            cur = cur.next.next;
        }
        return s.next;
    }

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

难点在于要删除倒数n个节点，就要拿到前一个节点的指针，也就是快指针走n+1步

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2 = s;
        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return s.next;
    }

环形链表 II

慢指针一次走一步，快指针一次走两步，慢指针能追上快指针就说明有环。

【注意】快指针在原地，慢指针到起点，同时走一步，相遇了，同时走一步，说明是环的入口，但是要考虑特殊情况：如果是环形链表，很明显，上一步才是环入口，所以要提前判断slow == fast。

public ListNode detectCycle(ListNode head) {
        ListNode slow = head; //慢指针
        ListNode fast = head; //快指针
        while(fast!=null && fast.next!=null){ //防止快指针走两步走到null了导致空指针，再加个判断
            slow = slow.next;
            fast = fast.next.next;
            //假如是环形链表，那么相等的位置就是入口
            if(slow == fast){ //第一次相遇
                //进入第二阶段，快指针留在原地，慢指针回到起点，再次相遇的时候就是入口
                slow = head;
                //快慢指针同时移动一步，直到相遇，就是入口
                while (true){
                    if(slow == fast){//第二次又相遇，说明是环形链表，所处的节点就是入口
                        return slow;
                    }
                    slow = slow.next;
                    fast = fast.next;
                }
            }
        }
        return null;
    }

面试题 02.07. 链表相交

这道题目难点在认识到：

• 双指针的路径长度相同，所以一定会相遇。

• 相遇点就是第一个公共节点（相交节点）。

• 不相交时，双指针会同时走到 null。

演示：

每个指针都走一步

链表B遍历完成了，开始遍历链表A

链表A遍历完成，开始遍历链表B

指针AB重合于公共交点，返回A即可

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 初始化两个指针，分别指向两个链表的头节点
        ListNode A = headA;
        ListNode B = headB;

        // 当两个指针不相遇时，继续循环
        while (A != B) {
            // 如果指针 A 走到链表 A 的末尾，则跳到链表 B 的头节点
            // 否则，继续向后移动
            A = (A == null) ? headB : A.next;

            // 如果指针 B 走到链表 B 的末尾，则跳到链表 A 的头节点
            // 否则，继续向后移动
            B = (B == null) ? headA : B.next;
        }

        // 循环结束时，A 和 B 要么指向相交节点，要么都为 null（不相交）
        return A;
    }