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

第二章?链表part02

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

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

• ?面试题?02.07.?链表相交?

• ?142.环形链表II?

• ?总结

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

用虚拟头结点，这样会方便很多。?

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

文章讲解/视频讲解：?代码随想录

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

双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向?第N个节点的前一个节点，建议先看视频。

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

文章讲解/视频讲解：代码随想录

?面试题?02.07.?链表相交??

本题没有视频讲解，大家注意?数值相同，不代表指针相同。

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

文章讲解：代码随想录

?142.环形链表II??

算是链表比较有难度的题目，需要多花点时间理解?确定环和找环入口，建议先看视频。

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

文章讲解/视频讲解：代码随想录

---

? ? ? ? c++代码示例如下

ListNode* swapPairs(ListNode* head) {
    ListNode* dumHead = new ListNode(0);
    dumHead->next = head;
    ListNode* cur = dumHead;
    while (cur->next != nullptr && cur->next->next != nullptr) {
        ListNode* tmp1 = cur->next;
        ListNode* tmp2 = cur->next->next->next;

        cur->next = cur->next->next;
        cur->next->next = tmp1;
        cur->next->next->next = tmp2;

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

? ? ? ? 双指针法，定义一个fast指针，一个slow指针。要删除倒数第n个节点，先让fast移动n步，然后fast和slow同时移动，直到fast指向链表末尾，此时删掉slow指向的节点即可。

注意细节：fast应该先走n+1步，为什么是n+1呢？因为只有这样同时移动的时候slow才能指向删除节点的上一个节点，方便做删除操作。

c++代码示例如下

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;
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* tmp = slow->next;
    slow->next = slow->next->next;
    delete tmp;
    return dummyHead->next;
}

c++代码示例如下

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

ListNode* detectCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            ListNode* index1 = fast;
            ListNode* index2 = head;
            while (index1 != index2) {
                index1 = index1->next;
                index2 = index2->next;
            }
            return index2;
        }
    }
    return NULL;
}