LeetCode刷题day4——链表part2

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

用pre代表第1个节点，cur代表它后面的相邻节点，tmp存储cur->next。
但是问题找不到怎么返回新的节点。想着就循环一次，在第一次交换的时候就确认新的头结点。但还存在很多问题，具体如下：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr)  return head;
        // 奇数空一个，偶数交换
        ListNode* newhead = nullptr;

        ListNode* pre = head;
        ListNode* cur = head->next;
        while (cur != nullptr) {
            ListNode* tmp = cur->next; // 得知道交换完的下一个节点在哪
            cur->next = pre;
            pre->next = tmp;
            int loop = 1;
            if (loop--) {
                newhead = cur;
            }
            // 交换完一次++2
            pre = tmp;
            cur = pre->next;//如果pre已经是最后一个节点了则错误
            //而且这样交换的话，1没指向4
        }
        return newhead;
    }
};

卡哥：建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* cur = dummyhead;

        while(cur->next!=nullptr && cur->next->next!=nullptr){
            //交换
            ListNode* tmp1 = cur->next;
            ListNode* tmp2 = cur->next->next->next;
            
            cur->next = cur->next->next;//step1
            cur->next->next = tmp1;//step2
            tmp1->next = tmp2;//step3

            cur = cur->next->next;
        }

        ListNode* result = dummyhead->next;
        delete dummyhead;
        return result;
    }
};

19.删除链表的倒数第N个节点

1、遍历链表求取长度；2、size-n循环到要删除的节点的前一个节点；3、判断链表只有1个节点和其他情况。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* cur1 = dummyhead;
        int size = 0;
        while (cur1->next != nullptr) {
            cur1 = cur1->next;
            size++;
        }

        int loop = size - n;
        ListNode* cur2 = dummyhead;
        while (loop--) {
            cur2 = cur2->next;
        }
        // 此时cur为删除的前一个节点
        if (cur2->next->next != nullptr) {//如果只有一个节点的情况
            ListNode* tmp = cur2->next;
            cur2->next = cur2->next->next;
            delete tmp;
        }else{
            cur2->next = nullptr;
        }
        
        return dummyhead->next;
    }
};

卡哥：双指针应用——如果要删除倒数第n个节点，让fast移动n+1步，然后让fast和slow同时移动，直到fast指向链表末尾，这样才能slow指向删除节点的前一个节点了。
（n+1这个移动的步数 的思路得深度思考吸收）

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //fast指针走n+1步，
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* fastindex = dummyhead;
        ListNode* slowindex = dummyhead;
        while(n>=0 && fastindex!=nullptr){
            fastindex = fastindex->next; 
            n--;       
        }
        
        //然后同时移动slow fast，fast到null，slow才能指向删除的前一个节点
        while(fastindex!=nullptr){
            fastindex = fastindex->next;
            slowindex = slowindex->next;
        }
        
        slowindex->next = slowindex->next->next;
        ListNode* res = dummyhead->next;
        delete dummyhead;//一般自己new的要delete掉
        return res;
    }
};

面试题 02.07. 链表相交

错误点1：交点不是数值相等，而是指针相等。问题1：不知道怎么查询对比
卡哥：我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置。此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。
根据卡哥思路自己写的代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int size_A = 0;
        int size_B = 0;
        //计算长度
        while(curA!=nullptr){
            size_A++;
            curA = curA->next;//忘记移动指针了
        }
        while(curB!=nullptr){
            size_B++;
            curB = curB->next;
        }
       //循环完cur在最后了需要重新赋值
       curA = headA;
       curB = headB;
        //循环到相同长度
        if(size_A>size_B && curA!=nullptr){
            int loop = size_A - size_B;
            while(loop--){
                curA = curA->next;
            }
        }else if(size_B>size_A && curB!=nullptr){
            int loop = size_B - size_A;
            while(loop--){
                curB = curB->next;
            }
        }
        
        //对比
        while(curA!=nullptr && curB!=nullptr){
            if(curA == curB){
                return curA;
            }else{
                curA = curA->next;
                curB = curB->next;
            }
        }
        //循环完没找到
        return nullptr;
        
    }
};

卡哥为了简化运算，可以直接对最大的一个操作：

 // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }

142.环形链表II（快慢指针）

快指针2个节点速度，慢指针1个节点速度，进入环1个节点的速度差，如果是别的可能就一直追不上了。

那么相遇时： slow指针走过的节点数为: x + y，为什么是x+y，而不是 x + 若干环的长度 + y 呢？图示，当慢指针（绿色）进入环的时候，快指针（红色）可以在环上的任意位置，最坏的情况就是快指针在慢指针前面一个结点，而按照相对运动来说，假设环有n个结点，则快指针相对慢指针运动n-1个单位时间即可追上。那么相等时间来说，慢指针最坏情况运动n-1个单位（不满一圈）就可以追上，所以是x+y。

fast指针走过的节点数：x + y + n (y + z)，
因为fast走得快，在slow还没进来环之前它可能自己已经转了很多圈了。所以+n(y+z)；n为fast指针在环内走了n圈才遇到slow指针，（y+z）为 一圈内节点的个数A。注意：n>=1。图示：最快情况下，慢指针刚进环下一个结点就被追上，此时fast走的路程为1*(y+z)+y。 我突然想到：可能有的人觉得最快应该是慢指针走到环入口的时候，快指针刚好已经提前走到环入口处了，那注意此时n不可能是0，如果是0，y=0，则x = x，相当于环入口那一刻相遇，但是x那一段线段路程，他两是不可能相遇的，所以n至少是1在里面转了一圈刚好到环入口才有可能相遇。

所以2*(x+y) = x+y+n(y+z)最终可以化解为x = (n - 1) (y + z) + z，当n=1时x=z，很重要这个信息，说明若有两个指针指向x和z的开始的话，他两同时移动，最后在环入口的时候相等；n>1时无非就是多转几圈，但最终还是环入口处相遇，所以其他转圈其实信息不重要，主要是看z=多少。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fastindex = head;
        ListNode* slowindex = head;
        while(fastindex!=NULL && fastindex->next!=NULL){//因为2步跳所以要判断2个
            fastindex = fastindex->next->next;
            slowindex = slowindex->next;
            if(fastindex == slowindex){
                //讲解中的x=z 两个指针出发在环入口相遇
                ListNode* index1 = fastindex;//存储相遇的点，此时快慢指针一样等于哪个都可以
                ListNode* index2 = head;//从头出发
                while(index1!=index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};