day4 24. 两两交换链表中的节点19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II 总结

资料来源：代码随想录 (programmercarl.com)

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

class Solution
{
private:
    /* data */
public:
    Solution(/* args */);
    ~Solution();
    struct ListNode
    {
        /* data */
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };


};

6.删除链表的倒数第N个节点,双指针法

    // 6. 删除链表的倒数第N个节点,双指针法
    ListNode *deleteTailN(ListNode *head, int index)
    {
        ListNode *fast = head;
        ListNode *slow = head;
        int n = index;
        while (n-- && fast != NULL)
        { // 忘记考虑链表不够长的情况
            fast = fast->next;
        }

        fast = fast->next; // !!!!!! fast再提前走一步，因为需要让slow指向删除节点的上一个节点
        while (fast != NULL)//判断的是fast如果不多走一步，slow会多走一步
        {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode *tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;

        return _dummyHead->next;
    }

7.链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

/**
 * @file t7.h
 * @author nrt ([email protected])
 * @brief 07. 链表相交
 * @version 0.1
 * @date 2023-12-01
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <iostream>

using namespace std;

class Solution
{
public:
    struct ListNode
    {
        /* data */
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    // 初始化链表
    Solution()
    {
        _dummyHead = new ListNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    };
    ~Solution();

    ListNode *_dummyHead;
    int _size;

    // 7.链表相交
    /**
     * @brief Get the Intersection Node object
     *          思路：求链表长度差值，如果相交的话，肯定是最后一段从某个结点开始，地址相同，
     *                  先求出差值，然后，长的先走差值个数，再一起走，比较结点地址
     * @param headA
     * @param headB
     * @return ListNode*
     */

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *aDummyHead = headA;
        ListNode *bDummyHead = headB;
        int aSize = 0;
        int bSize = 0;

        while (aDummyHead != NULL)
        {
            aDummyHead = aDummyHead->next;
            aSize++;
        }
        while (bDummyHead != NULL)
        {
            bDummyHead = bDummyHead->next;
            bSize++;
        }
        // 置到表头
        aDummyHead = headA;
        bDummyHead = headB;
        int cSize = 0;
        // 使得A为长链，减少代码量
        if (bSize > aSize)
        {
            swap(aSize, bSize);
            swap(aDummyHead, bDummyHead);
        }
        cSize = aSize - bSize;

        // A链先走cSize长度
        while (cSize--)
        {
            aDummyHead = aDummyHead->next;
        }
        // 开始比较A，B链的结点
        while (aDummyHead != NULL)
        {
            if (aDummyHead == bDummyHead)
            {
                return aDummyHead;
            }
            aDummyHead = aDummyHead->next;
            bDummyHead = bDummyHead->next; // 位移
        }
        return NULL;
    }
};

8.环形链表

数学得出的结论很精彩：从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

    // 8. 环形链表II：给定一个链表，返回链表开始入环的第一个节点。 
	//    如果链表无环，则返回 null。
    /**
     * @brief 
     *思路：
     *1.快慢指针法判断是否有环，快指针步长2，慢指针步长1，如果有环的话
     * ，就像操场跑步，都会相遇的
     *2.从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点，
     * 那么当这两个指针相遇的时候就是 环形入口的节点**。
     *
     * @param head
     * @return ListNode*
     */

    ListNode *detectCycle(ListNode *head)
    {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            // 如果有环，找到入口
            if (fast == slow)//1.
            {
                ListNode *index1 = fast;
                ListNode *index2 = head;//2.
                while (index1 != index2)
                {
                    index1 = fast->next;
                    index2 = head->next;
                    
                }
                return index1;
            }
        }
        return NULL;
    }

总结：

主要还是要搞清楚逻辑，知道现在操作的是链表的第几个指针

这个图是 代码随想录知识星球 (opens new window)成员：海螺人 (opens new window)，所画，总结的非常好，分享给大家。