代码随想录训练营第四天 24两两交换链表中的节点 19删除链表的倒数第n个节点 02链表相交 142环形链表

第一题：

原题链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

思路：

本题的思路就是用虚拟头节点指向第二个节点，然后再指向第一个节点，然后再指向第三个节点。本题的关键，要暂存几个节点：首先我们虚拟头结点指向第二个节点的时候，第一个节点就没人指向，所以需要暂存，当我们第二个节点指向第一个节点的时候，第三个节点也没人指向，也需要暂存。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr) return head;
        ListNode* dummy = new ListNode(0);
        dummy -> next = head;
        ListNode* cur = dummy;
        while(cur -> next != nullptr && cur -> next -> next != nullptr){
            //有两个节点需要暂存
            ListNode* temp1 = cur -> next;
            ListNode* temp2 = cur -> next -> next -> next;
            cur -> next = cur -> next -> next;
            cur -> next -> next = temp1;
            temp1 -> next = temp2;
            cur = cur -> next -> next;
        }
        return dummy -> next;
    }
};

第二题：

原题链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

思路：

首先定义虚拟头节点，指向head，然后定义快慢指针节点都指向dummyHead，然后快指针节点向后遍历n+1个位置。然后快慢指针同时向后遍历直到快指针节点指向nullptr，此时慢指针节点的位置就是要删除节点的前一个位置。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy -> next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        n += 1;
        while(n){
            fast = fast -> next;
            n--;
        }
        while(fast != nullptr){
            fast = fast -> next;
            slow = slow -> next;
        }
        slow -> next = slow -> next -> next;
        return dummy -> next;

    }
};

第三题：

原题链接：面试题 02.07. 链表相交 - 力扣（LeetCode）

思路：

首先定义两个操作节点A， B分别指向headA和headB。

如果A节点不等于B节点，判断A节点是否遍历到尾部，如果遍历到尾部即A==NULL，则将headB赋值给A，否则A一直向后遍历；同理判断B节点。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* a = headA , * b = headB;
        while(a != b){
            a = a == NULL ? headB : a -> next;
            b = b == NULL ? headA : b -> next;
        }
        return a;
    }
};

第四题：

原题链接：142. 环形链表 II - 力扣（LeetCode）

思路：

首先定义快慢指针都指向链表的头部，判断fast是否为空，并且fast->next是否为空，如果都不为空的话，快指针节点比慢指针节点多走一步，如果是有环的话快慢指针节点肯定会在环内相遇。此时从头节点和相遇节点以相同的步长遍历，相交的地方就是入环处。

代码如下：

/**
 * 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) {
        if(head == NULL || head -> next == NULL) return NULL;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast -> next != NULL){
            fast = fast -> next -> next;
            slow = slow -> next;
            if(fast == slow){
                ListNode* index = fast;
                ListNode* index1 = head;
                while(index != index1){
                    index = index -> next;
                    index1 = index1 -> next;
                }
                return index;
            }
        }
        return NULL;
    }
};