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

24. 两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/

public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode res = head.next;
        ListNode pre = new ListNode(Integer.MAX_VALUE);
        ListNode p = head;
        ListNode l = null;
        while (p != null && p.next != null){
            l = p.next.next;
            pre.next = p.next;
            p.next.next = p;
            p.next = l;
            p = l;
            pre = pre.next.next;
        }
        return res;
    }

19.删除链表的倒数第N个节点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return head;
        ListNode realHead = new ListNode(Integer.MAX_VALUE,head);
        ListNode pre = realHead;
        ListNode p = head;
        int size = 0;
        while (p != null){
            size++;
            p = p.next;
        }
        for (int i = 0; i < size - n; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return realHead.next;
    }

总结：倒数第n个 也就是正数第 size - n + 1个，pre经过size - n次循环能精准定位到要删除的结点的上一个结点。
面试题 02.07. 链表相交
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        HashSet<ListNode> set = new HashSet<>();
        while (pA != null){
            set.add(pA);
            pA = pA.next;
        }
        while (pB != null){
            if (set.contains(pB)) return pB;
            pB = pB.next;
        }
        return null;
    }

总结：经典的使用hash的题
142. 环形链表 II
https://leetcode.cn/problems/linked-list-cycle-ii/description/

public ListNode detectCycle(ListNode head) {
        ListNode p = head;
        HashSet<ListNode> set = new HashSet<>();
        while (p != null){
            set.add(p);
            if (set.contains(p.next)) return p.next;
            p = p.next;
        }
        return null;
    }

总结：hash法好爽，hash大法好