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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* Dummy_head = new ListNode();
        Dummy_head->next = head;
        ListNode* curr = Dummy_head;
        while(curr->next!=nullptr && curr->next->next!=nullptr){
            ListNode* tmp_1 = curr->next;//准备交换的相邻两个节点的第一个位置
            ListNode* tmp_2 = curr->next->next->next; //把不动的节点先存储起来，用于与交换后的链表链接起来。
            curr->next = curr->next->next; //第一步，把相邻节点的第二个节点移动到前面，
            curr->next->next = tmp_1; // 第二步，把相邻节点的第一个移动至后面
            curr->next->next->next = tmp_2 ; // 移动完成后需要把后面的节点连接起来
            curr = curr->next->next; //移动到下一组相连节点前的节点，为移动他们做准备
        }
        return Dummy_head->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int node_count = 0;
        ListNode* dummy_head =new ListNode();
        dummy_head->next = head;
        ListNode* curr = dummy_head;
        while(curr->next!=nullptr){
            node_count++;
            curr=curr->next;
        }
        int delet_index = node_count - n;
        curr = dummy_head;
        while(delet_index --){
            curr=curr->next;            
        }
        ListNode* tmp  = curr->next;
        curr->next = curr->next->next;
        delete tmp;
        tmp = nullptr;
        return dummy_head->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int slow_index = 0;
        int fast_index = 0;
        ListNode* dummy_head = new ListNode();
        dummy_head->next = head;
        ListNode* slow_node = dummy_head;
        ListNode* fast_node = dummy_head;
        while(n--&&fast_node!=nullptr){
            fast_node = fast_node->next;
        }
        fast_node = fast_node->next; //因为 slownode需要指向被删除节点的前一个位置
        while(fast_node!=nullptr){
            //同步移动
            fast_node = fast_node->next;
            slow_node = slow_node->next;
        }
        ListNode* tmp = slow_node->next;
        slow_node->next = slow_node->next->next;
        delete tmp;
        tmp = nullptr;
        return dummy_head->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //思路，计算出两个链表长度
        //数据与尾部对其
        //两者同时往后移动
        //当两者地址相等时退出，返回交点
        //遍历至尾部地址都没有相等则说明没交点，返回null；
        //求出链表A长度
        int length_A = 0;
        ListNode* currA = headA;
        int length_B = 0;
        ListNode* currB = headB;
        while(currA!=nullptr||currB!=nullptr){
            if(currA!=nullptr){
            currA = currA->next;
            length_A++;
            }
            if(currB!=nullptr){
            currB = currB->next;
            length_B++;
            }
        }
        //求出长度差
        int delta_length = fabs(length_A - length_B);
        currA = headA;
        currB = headB;
        //谁长移动谁
        while(delta_length --){
            if(length_A>length_B){
                currA = currA->next;
            }else{
                currB = currB->next;
            }
        }
        //此时两者位置已经对齐，找出地址相等的节点即可
        while(currA!=nullptr){
            if(currA == currB){
                return currA;
            }
            currA = currA->next;
            currB = currB->next;
        }
        return nullptr;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
    //双指针法
    ListNode* slow_node = head; //慢指针
    ListNode* fast_node = head; //快指针
    //如果链表没环，则快指针先到尾部
    while(fast_node!=nullptr&&fast_node->next!=nullptr){  
        slow_node = slow_node->next; //慢指针一次移动一个
        fast_node = fast_node->next->next;  //快指针一次移动两个     
        if(slow_node == fast_node){//有环必相遇
            //公式推导出这遍历方式当两个指针相等时便是环出口
            //x = (n-1)(y+z) +z
            //x = z
            ListNode* meet_node_index_A = head;
            ListNode* meet_node_index_B = fast_node;
            while(meet_node_index_A!=meet_node_index_B){
                meet_node_index_A= meet_node_index_A->next;
                meet_node_index_B = meet_node_index_B->next;
            }
            return meet_node_index_A;
        }
    }
    return nullptr;
    }
};