您现在的位置是：首页 >其他 >代码随想录算法训练营第四天|leetcode 24. 两两交换链表中的节点 ，19.删除链表的倒数第N个节点 ， 面试题 02.07. 链表相交， 142.环形链表II网站首页其他

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

学习： 帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点

这道题考察的就是节点的互换，使用虚拟头结点可以避免对头结点的特殊处理。整道题的流程图引用代码随想录里的图，十分形象。

在链表的操作中，我们通常使用指针来表示节点之间的关系。假设cur是当前节点的指针，则cur->next指向当前节点的下一个节点。

• 当我们遍历链表时，我们通常会从链表的头节点开始，依次访问每个节点，并且将当前节点的指针更新为下一个节点的指针，以实现链表的遍历。这时，cur->next指向的就是下一个节点。
• 而当我们在插入或删除节点时，我们需要改变节点之间的链接关系，这时cur->next指向的就是当前节点所指向的下一个节点的指针，它可以被用来修改相应的链接关系。

因此，cur->next指向的具体内容取决于我们正在进行的操作类型和当前节点的位置，这里比较容易迷糊。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {

        ListNode* dHead = new ListNode(0);//虚拟头结点
        dHead->next = head; //虚拟头结点指向第一个节点
        ListNode* cur = dHead; //cur指向虚拟节点
        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 dHead->next;
    }
};

这里需要注意的是 ，下面创建两个临时指针指向

 ListNode* temp1 = cur->next;
 ListNode* temp2 = cur->next->next->next;

因为虚拟节点要指向第二个节点，如果不用临时temp1创建临时指针指向第一个节点，那cur->next = cur->next->next;后第一个节点就成了野节点，找不到了，temp2同理。

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

学习： 链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点

这里我自己先写了一遍，就是先遍历设置index，然后算出倒数节点是整数的第几个，直接按照之前的index索引找到节点后删除，虽然通过了leetcode但是方法比较复杂。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head,int n) {
        ListNode* dHead = new ListNode(0);
        dHead->next = head;
        ListNode* p = dHead;
        int size = 0;
        while (p->next != nullptr)
        {
            p = p->next;
            size++;
            //cout << size << endl;
        }
        int index = size - n;//算出倒数节点是整数的第几个
        ListNode* cur = dHead;
        while (index--)
        {
            cur = cur->next;
        }
        ListNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        size--;
        return dHead->next;
    }
};

下面给出双指针的解法，这道题其实是双指针的经典应用。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        //slow->next = slow->next->next; 
        
        ListNode *tmp = slow->next;  C++释放内存的逻辑
        slow->next = tmp->next;
        delete nth;
        return dummyHead->next;
    }
};

具体思路如下

• 定义fast指针和slow指针，初始值为虚拟头结点
• fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）
• fast和slow同时移动，直到fast指向末尾fast = NULL
• 删除slow指向的下一个节点

leetcode 面试题 02.07. 链表相交

未完待续。。。

leetcode 142.环形链表II

未完待续。。。