算法随想Day4【链表】| LC24-两两交换链表中的节点、LC19-删除链表的倒数第N个节点、LC160-链表相交、LC142-环形链表Ⅱ

标签：head ListNode LC24 next 链表 curr 节点

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

有点像反转链表的思路，参考其中的思路，写出来了一个，但逻辑有点绕，而且对一条链表的开始的两个节点没有写出通用的代码。

我的思路是：设置虚拟头指针，curr从head开始，最后返回的是head->next
Carl讲解思路：设置虚拟头节点dummyhead，curr从dummyhead开始，通过curr操作后两个节点，每次循环curr向后移两个节点，返回的是dummyhead->next。

明显讲解中的解法，更具有通用性。对前两个节点来说，省去了我代码中多的那个if判断。

////自写
ListNode* swapPairs(ListNode* head)
{
    ListNode* curr = head;
    ListNode* prev = nullptr, *temp = nullptr;
    ListNode* ret = nullptr;
    if (nullptr == curr || nullptr == curr->next)
    {
        return head;
    }
    ret = head->next;
    while (curr != nullptr && curr->next != nullptr)
    {
        temp = curr->next->next;
        if (prev != nullptr)
        {
            prev->next = curr->next;
        }
        curr->next->next = curr;
        prev = curr;
        curr = temp;
        prev->next = curr;
    }

    return ret;
}

////Carl视频讲解
ListNode* swapPairs_Carl(ListNode* head)
{
    ListNode* dummyhead = new ListNode(0);
    dummyhead->next = head;
    ListNode* curr = dummyhead;
    ListNode* temp = nullptr, *temp1 = nullptr;
    if (nullptr == head || nullptr == head->next)
    {
        return head;
    }
    while (curr->next != nullptr && curr->next->next != nullptr)
    {
        temp = curr->next;
        temp1 = curr->next->next->next;
        curr->next = curr->next->next;
        curr->next->next = temp;
        temp->next = temp1;
        curr = curr->next->next;
    }

    return dummyhead->next;
}

递归思路：

////递归版本
struct ListNode* swapPairs(struct ListNode* head){
    //递归结束条件：头节点不存在或头节点的下一个节点不存在。此时不需要交换，直接返回head
    if(!head || !head->next)
        return head;
    //创建一个节点指针类型保存头结点下一个节点
    struct ListNode *newHead = head->next;
    //更改头结点+2位节点后的值，并将头结点的next指针指向这个更改过的list
    head->next = swapPairs(newHead->next);
    //将新的头结点的next指针指向老的头节点
    newHead->next = head;
    return newHead;
}

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

还是按照单链表那一套思路，先定义一个虚拟的头节点prev，放在head之前。
同时curr指针从head开始遍历，temp指针用于标志倒数第 N 个结点，count用于倒数序号的计数。
prev还有个特殊作用，即可用于索引指向随时可能被删除的temp节点

多定义的一个ListNode* ret = prev，用于固定标志着虚拟头节点的位置，最后返回的也是ret->next。开始没有定义ret，返回的是head，但如果输入是[1], 1时会导致head被删除后，就变成野指针了，发生段错误。

ListNode* removeNthFromEnd(ListNode* head, int n) 
{
    ListNode* curr = head;
    ListNode* temp = head;
    ListNode* prev = new ListNode(0);
    ListNode* ret = prev;	//固定标志着虚拟头节点的位置
    prev->next = head;
    int count = 1;
    if (nullptr == head)
    {
        return head;
    }
    while (curr != nullptr)
    {
        if (curr->next == nullptr && count >= n)
        {
            prev->next = temp->next;
            delete temp;
            break;
        }
        curr = curr->next;
        if (count >= n)
        {
            prev = prev->next;
            temp = temp->next;
        }
        count++;
    }
    return ret->next;
}

Carl快慢指针写法（一开始就让fast相比slow拉开n个节点的距离）：

ListNode* removeNthFromEnd_carl(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;
}

官方解析中的多一个思路：

使用栈先进后出的特性，

LC160. 链表相交

思路较简单，直接上代码

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    ListNode* pa = headA;
    ListNode* pb = headB;
    int lenA = 0, lenB = 0, len_span = 0;
    while (pa != nullptr)
    {
        lenA++;
        pa = pa->next;
    }
    while (pb != nullptr)
    {
        lenB++;
        pb = pb->next;
    }
    pa = headA;
    pb = headB;
    if (lenB > lenA)
    {
        swap(lenA, lenB);
        swap(pa, pb);
    }
    len_span = lenA - lenB;
    while (len_span--)
    {
        pa = pa->next;
    }
    while (pa != nullptr)
    {
        if (pa == pb)
        {
            return pa;
        }
        pa = pa->next;
        pb = pb->next;
    }
    
    return nullptr;
}

LC142. 环形链表Ⅱ

开始自己拿多几个例子做对比，发现快慢指针可以帮助链表找到是否有环，而且第一次相遇后继续走，直到第二次相遇可以统计出环中节点的数量。但是没考虑到快指针可能在环内循环了多圈才与慢指针相遇。

通过Carl视频讲解，理解了由公式 2(x+y) = x + y + n(y + z) 推出到 x = (n - 1)(y + z) + z的过程，两者在圈内相遇后，让index1和index2两个指针分别从头节点和相遇点以相同的速度出发，知道相遇的地方即为环形入口节点。

理解了原理，代码就比较容易写了

ode *detectCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
        if (slow == fast) {
            ListNode* index1 = fast;
            ListNode* index2 = head;
            while (index1 != index2) {
                index1 = index1->next;
                index2 = index2->next;
            }
            return index2; // 返回环的入口
        }
    }
    return NULL;
}

思考和总结：

无法高效获取长度，无法根据偏移快速访问元素，是链表的两个劣势。

然而面试的时候经常碰见诸如获取倒数第n个元素，获取中间位置的元素，判断链表是否存在环，判断环的长度等和长度与位置有关的问题。这些问题都可以通过灵活运用双指针来解决。

Tips：双指针并不是固定的公式，而是一种思维方式~

获取倒数第n个元素：先让快指针向前走n个节点
获取中间位置的元素：fast向前走两次，slow向前走一次，直到 fast 无法向后走两次。设链表有 n 个元素，那么最多移动 n/2 轮。当 n 为奇数时，slow 恰好指向中间结点。当 n 为偶数时，slow 恰好指向中间两个结点的靠前一个
链表是否存在环：快指针时慢指针速度的两倍，若有环，两者必在环内某点相遇
环的长度：统计第一次相遇到第二次相遇过程中，slow走的步数

（作者：Time-Limit，来源力扣（LeetCode）：https://leetcode.cn/problems/linked-list-cycle/solution/yi-wen-gao-ding-chang-jian-de-lian-biao-wen-ti-h-2/）

标签：head,ListNode,LC24,next,链表,curr,节点
From： https://www.cnblogs.com/Mingzijiang/p/17092024.html