• 代码随想录63——额外题目【链表】：234回文链表、143重排链表、141环形链表

    文章目录

    1.234回文链表

    参考：代码随想录，234回文链表；力扣题目链接

    1.1.题目

    在这里插入图片描述

    1.2.解答

    1.2.1.数组模拟方法

    最直接的想法，就是把链表装成数组，然后再判断是否回文。

    使用数组判断回文的时候，使用双指针法，分别从前往后、从后往前遍历，判断数字是否相等即可。

    1.2.2.反转后半部分链表法

    分为如下几步：

    • 用快慢指针，他们都从头节点出发，快指针走两步，慢指针走一步，快指针遇到终止位置时，慢指针就在链表中间位置
      注意：
      （1）如果有奇数个节点，最后快指针到达链表最后一个节点，慢指针到达中间节点。比如有5个节点1 2 3 4 5 ，跳两次，最后快指针到达节点5，慢指针到达节点3。然后划分链表前半部分有2个节点1 2，后半部分有3个节点3 4 5。
      （2）如果有偶数个节点，最后快指针到达最后一个节点的下一个nullptr指针，慢指针到达中间节点。比如有4个节点1 2 3 4，跳两次，最后快指针到达4的下一个位置nullptr，慢指针到达节点3。然后划分链表前半部分有两个节点1 2，后半部分有2个节点3 4。
    • 同时用pre记录慢指针指向节点的前一个节点，用来分割链表，pre表示前半部分链表的结尾节点
    • 将链表分为前后均等两部分，如果链表长度是奇数，那么后半部分多一个节点
    • 将后半部分反转 ，得cur2，前半部分为cur1
    • 按照cur1的长度，一次比较cur1和cur2的节点数值

    如图所示：在这里插入图片描述

    最后给出代码如下：

    bool isPalindrome(ListNode *head)
{
    if(head == nullptr || head->next == nullptr)   
        return true;

    // 1.寻找分割链表的位置
    ListNode* fast = head;
    ListNode* slow = head;
    ListNode* pre = head;
    while(fast && fast->next)
    {
        pre = slow;   // 先备份pre节点
        slow = slow->next;  // slow走一步
        fast = fast->next->next;   // fast走两步
    }

    // 2.此时slow为后半部分链表的head, pre为前半部分链表的结尾
    pre->next = nullptr;    // 把前半部分链表切分出来，方便后面while循环遍历
    ListNode* list1 = head;   // 前半部分链表顺序保持不变
    ListNode* list2 = reverseList(slow);   // 翻转后半部分链表
    
    // 3.以前半部分链表长度为基准，判断前后链表是否相等
    while(list1 != nullptr)
    {
        if(list1->val != list2->val)
            return false;
        list1 = list1->next;
        list2 = list2->next;
    }
    
    // 运行到这里说明前后链表相等，因此原链表就是回文链表
    return true;
}

// 翻转链表
ListNode* reverseList(ListNode* head)
{
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while(cur != nullptr)
    {
        ListNode* tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    2.143重排链表

    参考：代码随想录，143重排链表；力扣题目链接

    2.1.题目

    在这里插入图片描述

    2.2.解答

    2.2.1.数组模拟

    链表存在的问题就是只能单向的访问，所以如果想访问最后一个节点就需要把整个链表遍历完。但是这里又需要不断切换访问前后的节点，所以直接使用链表来访问是不行的，必须借助中间的数据结构。

    这里就是借助数组，先把链表的所有节点存储到数组中，然后遍历链表的节点的时候遍历数组就可以了，因为数组是可以利用索引随便访问前后的位置的。

    直接给出代码如下，前后访问数组的时候使用双指针就可以实现。

    // 1.解法一：使用数组存储ListNode，然后使用首尾双指针来修改list的指向
void reorderList(ListNode *head)
{
    if(head == nullptr)
        return;
    
    // 1.存储节点
    vector<ListNode*> vec;
    ListNode* cur = head;
    // 注意这里不需要存头结点，因为头结点位置是不动的
    while(cur->next != nullptr)
    {
        vec.push_back(cur->next);   
        cur = cur->next;
    }

    // 2.前后双指针重构链表
    cur = head;  // 头节点，不动
    int left = 0;   // 指向vec中节点的左指针
    int right = vec.size() - 1;  // 指向vec中节点的右指针
    int count = 0;   // 表示当前该存储左指针还是右指针
    while(left <= right)
    {
        if(count % 2 == 0)   // 存储右指针
            cur->next = vec[right--];
        else    // 存储左指针
            cur->next = vec[left++];
        cur = cur->next;  // 移动到下一个位置，修改下个节点的指向
        count++;
    }

    // 3.最后一个节点指向nullptr
    cur->next = nullptr;   
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    2.2.2.双向队列模拟

    这种方法和数组是同一个思想，只不过是使用双端队列，这样不用使用数组的双指针前后访问，其实本质上是没有什么不同的。

    // 2.解法二：使用双向队列存储，这样就可以首尾弹出，不用使用双指针了
void reorderList(ListNode *head)
{
    if(head == nullptr)
        return;
    
    // 1.存储节点
    deque<ListNode*> que;
    ListNode* cur = head;
    // 注意这里不需要存头结点，因为头结点位置是不动的
    while(cur->next != nullptr)
    {
        que.push_back(cur->next);   
        cur = cur->next;
    }

    // 2.使用deque前后访问节点，每访问一个节点之后就把它弹出
    cur = head;  // 头节点，不动
    int count = 0;   // 表示当前该存储左指针还是右指针
    while(!que.empty())
    {
        if(count % 2 == 0)   // 存储右指针
        {
            cur->next = que.back();
            que.pop_back();
        }
        else    // 存储左指针
        {
            cur->next = que.front();
            que.pop_front();
        }
        count++;
        cur = cur->next;
    }

    // 3.最后一个节点指向nullptr
    cur->next = nullptr;   
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    2.2.3.直接分割链表

    上面两种方法都使用了额外的空间来存储链表的节点，所以空间复杂度是O(n)。如果链表非常长，上面的方法就比较浪费空间了，虽然存储的是指针。

    所以一个进阶的解法就是要求原地修改链表，而不能有额外的空间消耗。

    方法就是将链表分割成两个链表，然后把第二个链表反转，之后在通过两个链表拼接成新的链表。

    如下图所示：

    在这里插入图片描述
    切割链表的操作和上一道题目是一样的，但是代码随想录中切割的解法和上一题又稍微有一点不同：

    • 上一题是对于链表切割的时候，如果是偶数节点自然两个链表都是相等的，如果是奇数节点则前链表长度比后链表长度 小1。

    • 但是这道题代码随想录上给出的解答是如果奇数节点则前链表长度比后链表长度 大1。

    这个实际是有道理的，可以方便编程。但是连续两道分割链表的题目又使用两种分割方法，感觉太繁琐不容易记忆。所以这里自己还是使用上一道题目的分割方法，即如果是奇数节点，则前链表长度比后链表长度 小1。

    • 如果原链表长度是奇数，如1 2 3 4 5：则前链表是1 2，后链表是3 4 5，翻转后是5 4 3。由于前链表的第一个节点一定是固定的，所以新的链表遍历的时候不需要访问前链表的第一个节点。那么访问的时候后链表5 4 3都需要访问，前链表只需要访问一个2。所以奇数情况下，需要访问的节点个数后链表比前链表多2个节点。
    • 如果原链表长度是偶数，如1 2 3 4：则前链表是1 2，后链表是3 4，翻转后是4 3。同理，后链表需要访问4 3，前链表只需要访问2。所以偶数情况下，需要访问的节点个数后链表比前链表多1个节点。

    因此在遍历链表的时候，分两个步骤：

    • 以 前链表节点非空 为循环条件，遍历完所有节点
    • 此时后链表一定剩余1或2个节点，然后再把所有的后链表剩余的节点遍历完即可。

    最后给出代码如下， 并不难，注意细节即可。

    // 3.解法三：拆分链表，把链表分成前后两部分，然后把后半部分翻转，然后依次
void reorderList(ListNode *head)
{
    if(head == nullptr || head->next == nullptr)
        return;
    
    // 1.快慢指针来拆分链表
    ListNode* fast = head;
    ListNode* slow = head;
    ListNode* pre = head;
    while(fast && fast->next)
    {
        pre = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    // 2.至此，pre是前一个链表的结尾，slow是后一个链表的开头
    // 注意cur2可能和cur1长度相等，也可能比cur1长度大1
    pre->next = nullptr;   // 把前一个链表的尾巴截断，方便后面遍历
    ListNode* cur1 = head->next;  // 注意为什么cur1从第二个开始：因为第一个一定是head，不会动的
    ListNode* cur2 = reverseList(slow);   // 后一个链表翻转

    // 3.开始遍历，重构链表
    int count = 0;
    ListNode* cur = head;
    // 注意此时要遍历的链表：如果原链表是奇数（假设是5），则分割后前2后3，要遍历的前1后3
    // 如果原链表是偶数（假设是4），则分割后前2后2，要遍历的前1后2。因此不管怎样都是前链表先遍历完
    while(cur1)
    {
        if(count % 2 == 0)  // 偶数
        {
            cur->next = cur2;
            cur2 = cur2->next;
        }
        else
        {
            cur->next = cur1;
            cur1 = cur1->next; 
        }
        cur = cur->next;
        count++;
    }

    // 4.处理cur2剩余的链表
    while(cur2)
    {
        cur->next = cur2;
        cur2 = cur2->next;
        cur = cur->next;
    }

    // 最后将链表收尾
    cur->next = nullptr;   
}

// 翻转链表
ListNode* reverseList(ListNode* head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode* cur = head;
    ListNode* pre = nullptr;
    while(cur)
    {
        ListNode* tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    3.141环形链表

    参考：代码随想录，141环形链表；力扣题目链接

    3.1.题目

    在这里插入图片描述

    3.2.解答

    这道题目在之前做过的 142环形链表II 中已经做过了，那道题目还要更难一些，因为判断了是否有环之后，还需要判断入环的节点，而这道题只需要判断是否有环，所以是142环形链表II的基础。

    判断是否有环的思想就是使用快慢指针：如果在遍历过程中这两个指针相遇，则有环；否则无环。

    直接给出代码如下，注意访问指针的时候判断是否有效。

    bool hasCycle(ListNode *head)
{
    ListNode* fast = head;
    ListNode* slow = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
            return true; 
    }

    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
  • 相关阅读:
    C/C++总结笔记——指针1：二级指针、空指针(NULL和nullptr)、野指针
    C++构造函数和析构函数
    Matlab .m脚本文件
    面视题之——索引失效
    4创建iSCSI共享存储
    Springboot定时任务热部署设计及实现
    【多级缓存】
    shell程序中常见的正规表达式
    数据结构中树、森林 与 二叉树的转换
    用QT做一个rtsp / rtmp实时流的播放器 ffmpeg
  • 原文地址：https://blog.csdn.net/qq_42731705/article/details/127997741