【算法刷题day4】Leetcode:24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II

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

文档链接：[代码随想录]
题目链接：24. 两两交换链表中的节点
状态：ok

题目：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
注意：
1.题目的意思是不能更改链表中节点的val值，只能改变指针的方向
2.每一次循环都分为三步
3.采用虚拟头节点将对头节点的操作等价于其他节点。但是要注意定义一个节点记录头节点指针用于返回，否则会出现以下问题。
4.我用了双指针，但貌似没比较用两个指针

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* k = new ListNode(0);
        k -> next = head;
        ListNode* i = k;
        ListNode* j = head;
        while(i->next != nullptr && i->next->next != nullptr){
            i -> next = j -> next;
            ListNode* temp = j -> next -> next;
            j -> next -> next = j;
            j -> next = temp;
            i = j;
            j = j -> next;
        }
        return k -> next;
    }
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }
};

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

文档链接：[代码随想录]
题目链接：19.删除链表中的倒数第N个节点
状态：ok 双指针

题目：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
注意：
1.本来想的是找快指针和慢指针的插值，当快指针移动到与慢指针距离达到一定长度时移动慢指针，但会出现快指针指向nullptr而慢指针少走一步的情况

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* node = new ListNode(0);
        node -> next = head;
        ListNode* lowindex = node;
        ListNode* fastindex = node;
        int l = 0, r = 0;
        while (fastindex != nullptr) {
                fastindex = fastindex->next;
                l++;
            while (l - r - 1 > n) {
                lowindex = lowindex->next;
                r++;
            }
        }
        ListNode* temp = lowindex->next;
        lowindex->next = lowindex->next->next;
        delete temp;
        return head;
    }
};

2.直接使快指针提前走几步之后快慢指针共同前进最简单。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* node = new ListNode(0);
        node -> next = head;
        ListNode* lowindex = node;
        ListNode* fastindex = node;
        while (fastindex != nullptr && n--) {
            fastindex = fastindex->next;
           
        } 
        fastindex = fastindex -> next;
        while (fastindex !=nullptr) {
            fastindex = fastindex->next;
            lowindex = lowindex->next;      
        }
        ListNode* temp = lowindex->next;
        lowindex->next = lowindex->next->next;
        delete temp;
        return node->next;
    }
};

面试题02.07.链表相交

文档链接：[代码随想录]
题目链接：面试题02.07.链表相交
状态：ok

题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
注意：
1.比较的是节点不是节点的值
2.第一次遍历后需要把指针复原并且要在交换两条链表之前复原指向头节点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != nullptr){
            lenA++;
            curA = curA -> next;
        }
        while(curB != nullptr){
            lenB++;
            curB = curB -> next;
        }
        curA = headA;
        curB = headB;
        if(lenA < lenB){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        while((lenA-lenB) > 0){
            curA = curA -> next;
            lenA--;
        }
        while(curA != nullptr){
            if(curA == curB){
                return curA;
            }
            curA = curA -> next;
            curB = curB -> next;
        }
        return NULL;
    }
};

142.环形链表

文档链接：[代码随想录]
题目链接：142.环形链表
状态：记住推导过程

题目：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
注意：
1.公式推导要理解

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};