代码随想录第四天 142.环形链表II面试题|| 02.07. 链表相交||19.删除链表的倒数第N个节点-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录第四天 142.环形链表II面试题|| 02.07. 链表相交||19.删除链表的倒数第N个节点。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

142.环形链表

题意：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

代码随想录第四天 142.环形链表II面试题|| 02.07. 链表相交||19.删除链表的倒数第N个节点

这个问题，可以用图示法来解决：

(1)首先慢指针在环内的第一圈和快指针相遇

(2)慢指针在环内经过n圈与快指针相遇，（其实无论转多少圈，和（1）效果是一样的）

快指针走过的长度为x+y+n*(z+y)

慢指针走过的长度为x+y

x+y+n*(x+y)=2*(x+y)

x=(n-1)*(y+z)+z

即从两个值指针分别从相遇点走,和从出发点走，重新的交汇点就是环的入口点。

代码如下：


class ListNodeSolution
{
public:  
    ListNode* whether_have_circleList(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                ListNode* index1 = head;
                ListNode* index2 = slow;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                cout << index2->val;
                return index2;
                //cout << index2;*/
            }
        }
        cout << "NULL";
        return NULL;
    }
};

时间复杂度为O(n)

02.07. 链表相交

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

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

代码随想录第四天 142.环形链表II面试题|| 02.07. 链表相交||19.删除链表的倒数第N个节点

代码如下：

 class Solution {
 public:
     ListNode* swapPairs(ListNode* head) {
         ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
         dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
         ListNode* cur = dummyHead;
         while (cur->next != nullptr && cur->next->next != nullptr) {
             ListNode* tmp = cur->next; // 记录临时节点
             ListNode* tmp1 = cur->next->next->next; // 记录临时节点

             cur->next = cur->next->next;    // 步骤一
             cur->next->next = tmp;          // 步骤二
             cur->next->next->next = tmp1;   // 步骤三

             cur = cur->next->next; // cur移动两位，准备下一轮交换
         }
         return dummyHead->next;
     }
 };

剩下的明日继续写文章来源地址https://www.toymoban.com/news/detail-491560.html

到了这里，关于代码随想录第四天 142.环形链表II面试题|| 02.07. 链表相交||19.删除链表的倒数第N个节点的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！