算法训练营Day 4

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

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/
文章讲解：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#_24-%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9
视频讲解：https://www.bilibili.com/video/BV1YT411g7br

考察点：链表基础， 这题很简单

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        ListNode* a = nullptr;
        ListNode* b = nullptr;
        while(cur->next!=nullptr && cur->next->next!=nullptr){
            a = cur->next;
            b = a->next;
            a->next = b->next;
            b->next = a;
            cur->next = b;
	    # 跳转两个节点
            cur = a;
        }
        return dummyHead->next;
    }
};

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

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/submissions/
文章讲解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html#_19-%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACn%E4%B8%AA%E8%8A%82%E7%82%B9
视频讲解：https://www.bilibili.com/video/BV1vW4y1U7Gf

考察点：链表基础，双指针

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        
        ListNode* left = dummyHead;
        ListNode* right = dummyHead;

        for(int i=0; i<n; i++){
            right = right->next;
        }
        while(right->next!=nullptr){
            left = left->next;
            right = right->next;
        }
        
        ListNode* tmp = left->next;
        left->next = tmp->next;
        delete tmp;
        return dummyHead->next;
    }
};

160.链表相交
题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/submissions/
文章讲解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html#%E6%80%9D%E8%B7%AF

考察点：链表基础

先遍历计算长度，因为重合部分长度相同，故将长链先移动至剩余部分和短链相等。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* dummyHeadA = new ListNode();
        dummyHeadA->next = headA;
        ListNode* dummyHeadB = new ListNode();
        dummyHeadB->next = headB;

        ListNode* curA = dummyHeadA;
        ListNode* curB = dummyHeadB;
        int a = 0;
        int b = 0;
        int diff = 0;

        while(curA!=nullptr){
            curA= curA->next;
            a++;
        }

        while(curB!=nullptr){
            curB = curB->next;
            b++;
        }

        if(a>b){
            diff = a-b;
            curA = dummyHeadA;
            curB = dummyHeadB;
        }else{
            diff = b-a;
            curA = dummyHeadB;
            curB = dummyHeadA;
        }

        while(diff--){
            curA = curA->next;
        }

        while(curA!=nullptr){
            if(curA==curB){
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        
        return nullptr;
    }
};

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

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/
文章讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF
视频讲解：https://www.bilibili.com/video/BV1if4y1d7ob

考察点：本提较难，先判断有无交点，在通过一点点数学技巧计算出交点位置。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode* left = dummyHead;
        ListNode* right = dummyHead;
        while(right!=nullptr&&right->next!=nullptr){
            left=left->next;
            right=right->next->next;
            if(left==right){
                left=dummyHead;
                while(left!=right){
                    left=left->next;
                    right=right->next;
                }
                return left;
            }
        }
        return nullptr;
    }
};