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

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

题目链接: LeetCode 24

思路: 交换结点前将cur后第一个结点和第三个结点进行保存，然后修改cur指向头节点后再修改头节点后的结点

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* temp1=cur->next; // 修改cur->next时会丢失结点，所以将结点进行保存
            ListNode* temp3=cur->next->next->next;

            cur->next=cur->next->next;
            cur->next->next=temp1;
            temp1->next=temp3;


            cur=cur->next->next; 
        }
        return dummyHead->next;
    }
};

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

题目链接: LeetCode19

思路: 使用双指针，看注释画图

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* fast=dummyHead; // 设置快慢指针，让快慢指针指向虚拟结点
        ListNode* slow=dummyHead;

        while(n-- && fast!=nullptr){ // 让快指针多走n+1步
            fast=fast->next;
        }
        fast=fast->next; // 走了n步后再走一步

        while(fast!=nullptr){ // 当快指针指向nullptr时，slow指针正好指向n-1的位置
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummyHead->next;
    }
};

LeetCode 142.环形链表II

题目链接: LeetCode142.环形链表II

思路: 使用快慢指针，令快指针2步走，如果说存在链表环路的话则快指针和满指针一定会相遇，不存在环路则直接返回空指针。

快慢指针相遇后，则将其中一个指针置为head，然后是他们以同样的速度进行前进，做循环判断(fast!=slow)，退出循环则表示相等，直接返回从头节点开始的指针即可。

/**
 * 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* fast=head;
        ListNode* slow=head;
        while(true){ 
            if(fast==nullptr||fast->next==nullptr) return nullptr;  //fast指针为空指针则没有环路
            fast=fast->next->next; // 这里是已经知道链表存在环路了，令fast两步走
            slow=slow->next;
            if(fast==slow) break; // 相遇
        }
        slow=head; // 将慢指针置为头节点，然后使慢指针和快指针按一位往前走
        while(slow!=fast){ 
            fast=fast->next;
            slow=slow->next;
        }
        return slow; // 循环执行完成则表示找到入口了，直接返回slow即可
    }
};