链表篇

class Solution {
public:
    //翻转链表
    //输入：head = [1,2,3,4,5]
    //输出：[5,4,3,2,1]

    //双指针法
    ListNode *reverseList(ListNode *head) {
        ListNode *cur = head;
        ListNode *pre = NULL;
        ListNode *tmp = cur;//保存变量
        while (cur) {
            tmp = cur->next;//保存原来的下一个指向
            cur->next = pre;//将下一个指向改为pre
            pre = cur;//修改pre往前移动一格
            cur = tmp;//修改cur往前移动一格
        }
        return pre;
    }

    //递归法
    ListNode *reverse(ListNode *cur,ListNode *pre){
        if(cur == NULL) return pre;
        ListNode *tmp= NULL;
        tmp=cur->next;
        cur->next=pre;
        return reverse(tmp,cur);
    }
};

#include "../cunion.h"
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode * dummyHead=new ListNode();
        dummyHead->next=head;
        ListNode *fast=dummyHead->next;
        ListNode *slow=dummyHead->next;
        while (fast!= nullptr&& fast->next!= nullptr){
            fast=fast->next->next;
            slow=slow->next;
            if (fast==slow){
                ListNode *pos=fast;
                ListNode *run=head;
                while (run!=pos){
                    pos=pos->next;
                    run=run->next;
                }
                return run;
            }
        }
        return nullptr;
    }
};

#include "../cunion.h"
class Solution {
public:
    //输入：head = [1,2,3,4]
    //输出：[2,1,4,3]
    ListNode* swapPairs(ListNode* head) {
        ListNode *pre=new ListNode(0);
        pre->next=head;
        ListNode *cur=pre;
        ListNode *tmp=cur;
        ListNode *tmp1=cur;
        while (cur->next != nullptr && cur->next->next != nullptr){
            tmp=cur->next->next;
            tmp1=tmp->next;
            tmp->next=cur->next;
            cur->next=tmp1;
            cur=tmp1;
        }
        return pre->next;
    }
};

//
// Created by 春江花朝秋月夜 on 2024/3/23.
//
#include "../cunion.h"

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA;
        ListNode *B = headB;
        int lenA = len(A);
        int lenB = len(B);
        ListNode *curA = headA;
        ListNode *curB = headB;
        if (lenA > lenB) {
            int diff = lenA - lenB;
            return findInsect(curA,curB,diff);
        } else if (lenB > lenA) {
            int diff = lenB - lenA;
            return findInsect(curB,curA,diff);
        } else if (lenA == lenB) {
            return findInsect(curA,curB,0);
        }
        return nullptr;
    }

    ListNode *findInsect(ListNode *left,ListNode *right,int diff){
        while (diff--){
            left=left->next;
        }
        if (left!=right){
            while (left!= nullptr){
                if (left==right){
                    return left;
                }
                left=left->next;
                right=right->next;
            }
        } else{
            return left;
        }
        return nullptr;
    }
    int len(ListNode *node) {
        int len = 0;
        while (node != nullptr) {
            node = node->next;
            len++;
        }
        return len;
    }
};

//
// Created by 春江花朝秋月夜 on 2024/3/21.
//
//删除链表的倒数第n个节点
#include "../cunion.h"

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummyHead = new ListNode(0, head);
        int len = 0;
        ListNode *node = dummyHead->next;
        while (node) {
            len++;
            node = node->next;
        }
        ListNode *travelNode = dummyHead->next;
        //因为是通过倒数来实现计数，所以索引从1开始
        for (int i = 1; i < len - i + 1; ++i) {
            travelNode = travelNode->next;
        }
        travelNode->next = travelNode->next->next;
        return dummyHead->next;
    }
    //使用双指针来解决这个问题！！！
    ListNode* removeNthFromEndWithDouble(ListNode* head, int n) {
        ListNode *dummyHead=new ListNode(0);
        dummyHead->next=head;//虚拟头节点

        ListNode *fast=dummyHead;
        ListNode *slow=dummyHead;

        //fast向前移动n步
        while (fast!= NULL&&n--){
            fast=fast->next;
        }
        fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next=slow->next->next;
        return dummyHead->next;
    }
};

/** 采用虚拟头节点来解决的方法：
* ListNode *removeNthFromEnd(ListNode *head, int n) {
        //使用双指针来解决这个问题！！！
        ListNode *dummyHead = new ListNode(0, head);
        int len = 0;
        ListNode *node = dummyHead->next;
        while (node) {
            len++;
            node = node->next;
        }
        ListNode *travelNode = dummyHead->next;
        //因为是通过倒数来实现计数，所以索引从1开始
        for (int i = 1; i < len - i + 1; ++i) {
            travelNode = travelNode->next;
        }
        travelNode->next = travelNode->next->next;
        return dummyHead->next;
    }
*/