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

public ListNode swapPairs3(ListNode head) {
        //交换两个结点到底要改变几个指针？
        //两个结点之间的指针要反向，并且这对节点的前一个结点要重新指向新结点，这对结点指向后一个结点的指针也会改变
        //所以要提前保存前一个结点和后一个结点
        //既然涉及到前一个结点的操作了，那么就可以构造一个虚拟头节点
        ListNode tmpHead = new ListNode(0, head);
        ListNode cur = head;
        ListNode pre = tmpHead;
        ListNode next;
        while (cur != null && cur.next != null) {
            next = cur.next.next;
            //指针一个一个改
            pre.next = cur.next;
            cur.next.next = cur;
            cur.next = next;
            pre = cur;
            cur = cur.next;//交换之后指针的位置已经相当于往后挪动了
        }
        return tmpHead.next;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        //怎么删除倒数第n个结点，关键在于如何判断当前结点是倒数第n个，倒数第n个就是从尾巴往回走n步
        //一般来说，正数第n个很好判断，倒数第n个就需要两个指针了
        //慢指针和快指针之间相差n步，让快指针走到头，慢指针所在的位置就是倒数第n个
        ListNode fast = head;
        ListNode slow=head;
        while (n > 1) {
            fast = fast.next;
            n--;
        }
        ListNode tmpHead = new ListNode(0, head);
        ListNode pre = tmpHead;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
            pre = pre.next;//保存前一个指针
        }
        pre.next = slow.next;
        return tmpHead.next;
    }

         ListNode fast = head;
        // ListNode slow=head;
        while (n > 1) {
            fast = fast.next;
            n--;
        }
        ListNode tmpHead = new ListNode(0, head);
        ListNode pre = tmpHead;
        while (fast.next != null) {
            fast = fast.next;
            // slow = slow.next;
            pre = pre.next;//保存前一个指针
        }
        // pre.next = slow.next;
        pre.next = pre.next.next;
        return tmpHead.next;

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        //两个链表在一个地方相交，那么链表A的长度假设是a+c，链表B的长度假设是b+c
        //那么A走到头之后再走b步，B走到头之后再走a步；两个指针走的距离一定是相等的，妙不妙
        //妙啊
        if (headA == null || headB == null) {
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;
        int count = 0;
        while (count < 2) {

        }
        if (count == 2) {
            return null;
        }
        return a;
    }

public ListNode detectCycle2(ListNode head) {
        //这道题的主要思路是用快慢指针，一个指针每次走两步，一个指针每次走一步
        //如果有环的话，这两个指针一定会相遇，为什么呢？
        // 因为快指针先进入环中，慢指针后进入环内，那么快指针相对于慢指针的移动速度是一步，快指针一定会追上慢指针
        // 慢指针遍历完一圈环的时候，快指针一定走了两圈了，由于我们应该考虑相对运动速率
        //所以在这个过程中快指针一定会经过慢指针
        //综上，慢指针走过的路程=2(x+y)=快指针走过的路程=x+y+n(y+z)
        //化简一下：x+y=n(y+z)=> x=n(y+z)-y=> x=(n-1)(y+z)+z
        //这说明，一个指针从环内相遇的位置出发，另一个指针从头出发，两者一定会在环的入口相遇
        //我们这里判断的依据就是指针走过的距离一定相等，所以此时指针移动的速率一定要保持一致
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                slow = head;
                while (slow != fast) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }