/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) { 
        // 设置虚拟头结点
        ListNode dummynode = new ListNode(0);
        dummynode.next = head;
        // 设置当前节点cur
        ListNode cur = dummynode;
        // 循环退出条件：
        while (cur.next != null && cur.next.next != null){
            // 两两交换
            ListNode node1 = cur.next;
            ListNode node2 = node1.next;
            cur.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            cur = node1;
        }
        return dummynode.next;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 双指针法
        ListNode dummy = new ListNode(0, head);
        ListNode fast = head;
        ListNode slow = dummy;
        // fast 先向前n步
        for (int i = 0; i < n; i++){
            fast = fast.next;
        }
        // slow fast 同步向前遍历，直到fast到底为null，注意slow和fast之间的间距为n+1
        while (fast!= null){
            fast = fast.next;
            slow = slow.next;
        }
        // 删除slow.next 节点
        slow.next = slow.next.next;
        return dummy.next;
    }
}

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 方法一 先遍历两个链表，求出差值，尾部对齐，再从对齐处开始往遍历，找第一次重合即可
        ListNode a = headA;
        ListNode b = headB;
        // 求出两个链表的长度
        int lenA = 0;
        int lenB = 0;
        while (a != null) {
            a = a.next;
            lenA++;
        }
        while (b != null) {
            b = b.next;
            lenB++;
        }
        // 重置头结点
        a = headA;
        b = headB;
        // 让a为长链
        if (lenA < lenB) {
            // 1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            // 2. swap (curA, curB);
            ListNode tmpNode = a;
            a = b;
            b = tmpNode;
        }

        // 求长度差
        int gap = lenA - lenB;
        // a先动，对齐
        while (gap > 0) {
            a = a.next;
            gap--;
        }

        // 一起动
        while (a != null) {
            if (a == b) {
                return a;
            }
            a = a.next;
            b = b.next;
        }
        return null;

        // // 方法二 双指针 一个先遍历a然后遍历b，另一个先遍历b然后遍历a，第一次重合即可
        // ListNode node1 = headA;
        // ListNode node2 = headB;
        // while (node1 != node2){
        //     if (node1 == null){
        //         node1 = headB;
        //     }else{
        //         node1 = node1.next;
        //     }

        //     if (node2 == null){
        //         node2 = headA;
        //     }else{
        //         node2 = node2.next;
        //     }
        // }
        // return node1;
    }
}

class Solution {
    public ListNode detectCycle(ListNode head) {
        // 方法1 哈希表
        // 当前节点cur
        ListNode cur = head;
        // 哈希表
        Set<ListNode> visited = new HashSet<ListNode>();
        // cur遍历，存到哈希表内，出现重复的就是环入口
        while (cur != null){
            if (visited.contains(cur)){
                return cur;
            }else{
                visited.add(cur);
            }
            cur = cur.next;
        }
        return null;
        // 方法2 快慢指针
        // 暂时无法理解
    }
}