侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第四天 | 两两交换链表中的节点;删除链表的倒数第N个节点;链表相交;环形链表II

thinkTV
2023-04-22 / 0 评论 / 0 点赞 / 1,532 阅读 / 1,455 字 / 正在检测是否收录...

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

代码随想录:原文

力扣题目: 24. 两两交换链表中的节点

图片-1682146898005

1.1 思路

  • 使用虚拟头结点cur,不需要对针对头结点单独处理
  • 交换相邻两个元素
  • cur移动两位,准备下一轮交换
  • 当数组为偶数时,终止条件为cur->next为空
  • 当数组为奇数时,终止条件为cur->next->next为空

图片-1682149175532

注意: 链表问题要多画图

1.2 代码实现

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;
    }
};

注意:循环判断条件while(cur->next != nullptr && cur->next->next != nullptr)中cur->next是否为空的判断要先于cur->next->next,防止报错。

  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)

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

代码随想录:原文

力扣题目: 19.删除链表的倒数第N个节点

图片-1682153359562

2.1 思路

  • 删除目标节点,操作指针一定指向目标节点的前一个结点
  • 使用虚拟头结点cur,不需要对针对头结点单独处理
  • 定义fast指针和slow指针
  • fast首先走n + 1步,fast和slow同时移动,直到fast指向末尾。此时slow指向删除节点的上一个节点
  • 删除slow指向的下一个节点

图片-1682153877778
图片-1682153900555
图片-1682153906287

2.2 代码实现

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;
        }
        //C++释放内存的逻辑
        ListNode *tmp = slow->next;  
        slow->next = tmp->next;
        delete tmp;
        return dummyHead->next;
    }

注意: 释放删除内存

3. 链表相交

代码随想录:原文

力扣题目: 面试题 02.07. 链表相交

图片-1682154470474

3.1 思路

  1. 两个链表交点节点的指针,不是数值相等,而是指针相等
  2. 两个链表相交,则两个链表结尾一定有重和,数值和对应指针都相等
  3. curA移动到,和curB 末尾对齐的位置
    图片-1682154866209
  4. curA和curB是否相同,如果不相同,同时向后移动curA和curB,如果遇到curA == curB,则找到交点

3.2 代码实现

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头,lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上(末尾位置对齐)
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB,遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};
  • 时间复杂度:O(n+m)O(n + m)
  • 空间复杂度:O(1)O(1)

4. 环形链表

代码随想录:原文

力扣题目: 142.环形链表II

图片-1682155119651

4.1 思路

双指针法
1. 判断链表是否有环

  • 分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点
  • 如果 fast 和 slow指针在途中相遇 ,说明这个链表有环
  • fast指针一定先进入环中,如果fast指针和slow指针一定在环中相遇

数学证明参考代码随想录:原文

2. 找到这个环的入口

  • 头结点出发一个指针,从相遇节点也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是环形入口的节点

数学证明参考代码随想录:原文

哈希表法

  • set容器实现了一个哈希表,将指针地址存入set容器
  • 指针移动,新指针地址与set容器内指针比较,发现重复的就是环的入口。
  • 虽然简单,但时间复杂度高

图片-1682159213959

4.2 代码实现

双指针法

class Solution {
public:
    ListNode *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;
    }
};

数学结论需要记牢

哈希表法

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;//哈希表用于存放节点地址
        ListNode* cur=head;
        while(cur!=NULL){
            if(s.find(cur)!=s.end()){
                return cur;
            }else{
                s.insert(cur);
                cur=cur->next;
            }
        }
        return NULL;
    }
};

5. 总结

  • 善于使用虚拟头节点
  • 链表问题要多画图
  • 删除目标节点,操作指针一定指向目标节点的前一个结点
  • 循环判断条件注意判断顺序防止报错
  • 数学结论需要记牢

学习时间:130min

0

评论区