随想录刷题第四天 | 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II

24. 两两交换链表中的节点
    前后节点

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode dom = new ListNode();
        ListNode priv = null;
        ListNode end = dom;
        dom.next = head;
        
        while (end.next!=null && end.next.next != null){
            //翻转链表的前一个节点
            ListNode old = end;
            priv = end.next;
            end = end.next.next;
            //翻转链表的后一个节点 可能为null
            ListNode next = end.next;
            
            //翻转
            old.next = end;
            end.next = priv;
            priv.next = next;
            
            //已经翻转了
            end = priv;
        }
        
        return dom.next;
    }

19.删除链表的倒数第N个节点
快慢指针

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode end = null;
        ListNode front = head;
        
        n--;
        while(n>0){
            n--;
            front = front.next;
        }
        
        if (front.next == null){
            return head.next;
        }
        
        front = front.next;
        end = head;
        
        while (front.next != null){
            front = front.next;
            end = end.next;
        }
        
        end.next = end.next.next;
        
        return  head;
    }

面试题 02.07. 链表相交
设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，
则有：
头节点 headA 到 node 前，共有 a−c 个节点；
头节点 headB 到 node 前，共有 b−c 个节点；
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b+(a−c)

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

142.环形链表II
设fast每次走两步，solw每次走一步；
设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点。设两指针分别走了 f，s 步,当两者相遇时则有

1. fast 走的步数是slow步数的 2 倍，即 f=2s；（解析： fast 每轮走 2 步）
2. fast 比 slow多走了 n 个环的长度，即 f=s+nb。
   所以: f=2nb，s=nb.

此时将如果将慢指针前进a步即a+nb，则到达环的入口处

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        //
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }