【C/C++数据结构】链表与快慢指针

这篇具有很好参考价值的文章主要介绍了【C/C++数据结构】链表与快慢指针。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、单链表

二、双向循环链表

三、判断链表是否带环

四、链表的回文结构判断

五、复制带随机指针的链表


一、单链表

优点:头部增删效率高,动态存储无空间浪费

缺点:尾部增删、遍历效率低,不支持随机访问节点

头结点:单链表头结点可有可无,带头结点更方便进行初始化

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int NodeData;

typedef struct List 
{
    NodeData data;
    struct List* next;
}List;

void Init(List* list) 
{
    assert(list);
    list->next = (List*)malloc(sizeof(List));    // 空头结点
    list->next->next = NULL;
}

bool Empty(List* list) 
{
    assert(list);
    return list->next->next == NULL;
}

void Push(List* list, NodeData x) 
{
    assert(list);
    List* node = (List*)malloc(sizeof(List));
    if (node == NULL) 
    {
        perror("malloc");
        return;
    }
    node->data = x;
    node->next = list->next->next;
    list->next->next = node;
}

void Pop(List* list) 
{
    assert(list);
    if (!Empty(list)) 
    {
        List* cur = list->next->next;
        list->next = cur->next;
        free(cur);
        cur = NULL;
    }
}

size_t Size(List* list) 
{
    assert(list);
    size_t size = 0;
    List* cur = list->next->next;
    while (cur) 
    {
        ++size;
        cur = cur->next;
    }
    printf("the list size = %d\n", size);
    return size;
}

void PrintList(List* list) 
{
    assert(list);
    if (!Empty(list)) 
    {
        List* cur = list->next->next;
        printf("%d ", cur->data);
        while (cur->next) 
        {
            printf("-> %d ", cur->next->data);
            cur = cur->next;
        }
        printf("\n");
    }
}

int main() 
{
    List list;
    Init(&list);
    Push(&list, 1);
    Push(&list, 3);
    Push(&list, 5);
    Push(&list, 7);
    Size(&list);
    PrintList(&list);
    Pop(&list);
    Pop(&list);
    Pop(&list);
    Pop(&list);
    Pop(&list);
    Size(&list);
    PrintList(&list);
    return 0;
}

二、双向循环链表

特征:

  • 每个Node都有一个data值,一个prev前驱指针和一个next后置指针
  • C++的STL中封装的就是双向循环链表
  • 头部增删和尾部增删效率一样高,但依然不支持随机访问
  • 链表循环且带头结点,最后一个Node指向头结点,头结点也指向最后一个Node
  • 空链表的前驱和后置指针都指向头结点,头结点不存放数据

代码分析:

Push和Pop函数通过调用Insert和Erase函数对Node进行按址增删,减少了代码的复用

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int NodeData;

typedef struct List 
{
    NodeData data;
    struct List* prev;
    struct List* next;
}List;

void Init(List* list) 
{
    assert(list);
    list->prev = list;
    list->next = list;
}

bool Empty(List* list) 
{
    assert(list);
    return list->next == list;
}

void Insert(List* list, NodeData x, List* pos) 
{
    assert(list && pos);
    List* prev = pos->prev;
    List* node = (List*)malloc(sizeof(List));
    if (node == NULL) 
    {
        perror("malloc");
        exit(1);
    }
    node->data = x;
    node->next = pos;
    pos->prev = node;
    node->prev = prev;
    prev->next = node;
}

void Erase(List* list, List* pos) 
{
    assert(list && pos);
    List* prev = pos->prev;
    List* next = pos->next;
    prev->next = next;
    next->prev = prev;
    free(pos);
    pos = NULL;
}

void PushFront(List* list, NodeData x) 
{
    assert(list);
    Insert(list, x, list->next);
}

void PushBack(List* list, NodeData x) 
{
    assert(list);
    Insert(list, x, list);
}

void PopFront(List* list) 
{
    assert(list);
    Erase(list, list->next);
}

void PopBack(List* list) 
{
    assert(list);
    Erase(list, list->prev);
}

size_t Size(List* list) 
{
    assert(list);
    size_t size = 0;
    List* cur = list->next;
    while (cur != list) 
    {
        ++size;
        cur = cur->next;
    }
    printf("the list size is %d\n", size);
    return size;
}

void PrintList(List* list) 
{
    assert(list);
    if (!Empty(list)) 
    {
        List* cur = list->next;
        printf("%d ", cur->data);
        while (cur->next != list) 
        {
            printf("-> %d ", cur->next->data);
            cur = cur->next;
        }
        printf("\n");
    }
}

int main() 
{
    List list;
    Init(&list);
    PushFront(&list, 1);
    PushFront(&list, 3);
    PushFront(&list, 5);
    PushBack(&list, 2);
    PushBack(&list, 4);
    PushBack(&list, 6);
    Size(&list);
    PrintList(&list);   //5 -> 3 -> 1 -> 2 -> 4 -> 6

    PopFront(&list);
    PopBack(&list);
    PopBack(&list);
    PushFront(&list, 10);
    PushBack(&list, 20);
    Size(&list);
    PrintList(&list);   //10 -> 3 -> 1 -> 2 -> 20
    return 0;
}

三、判断链表是否带环

链表带环:尾结点指向链表的某个节点

函数设计:设置快慢指针,根据链表头结点head,判断链表是否带环,返回bool值

bool IsCircle(struct ListNode* head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next) 
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) 
            return true;
    }
    return false;
}

四、链表的回文结构判断

函数要求:时间复杂度为O(n), 额外空间复杂度为O(1), 返回bool值

函数设计:文章来源地址https://www.toymoban.com/news/detail-595972.html

  1. 用快慢指针找到链表中间节点
  2. 将中间节点之后的链表逆置
  3. 设置头指针和中间节点指针进行回文判断
  4. 将中间节点之后的链表再次逆置, 还原链表结构
struct ListNode* MidNode(struct ListNode* head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next) 
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

struct ListNode* ReverseList(struct ListNode* head) 
{
    struct ListNode* p1 = NULL;
    struct ListNode* p2 = head;
    struct ListNode* p3 = NULL;
    if (p2 != NULL) 
        p3 = head->next;
    while (p3) 
    {
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        p3 = p3->next;
    }
    p2->next = p1;
    p1 = p2;
    p2 = p3;
    return p1;
}

bool ChkPalindrome(struct ListNode* A) 
{
    struct ListNode* mid = MidNode(A);
    mid = ReverseList(mid);
    struct ListNode* front = A;
    struct ListNode* back = mid;
    struct ListNode* cur = back;
    int flag = 1;
    while (back && front != cur) 
    {
        if (front->val != back->val) 
        {
            flag = 0;
            break;
        }
        front = front->next;
        back = back->next;
    }
    mid = ReverseList(mid);    //再次逆置,防止链表结构被破坏
    if (flag == 0)
        return false;
    return true;
}

五、复制带随机指针的链表

函数要求:

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。 深拷贝应该正好由 n 个全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。

每个节点用一个 [val, random_index] 表示:

        val:一个表示 Node.val 的整数。

        random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

【C/C++数据结构】链表与快慢指针,C/C++数据结构,链表,c语言,c++,数据结构

【C/C++数据结构】链表与快慢指针,C/C++数据结构,链表,c语言,c++,数据结构

【C/C++数据结构】链表与快慢指针,C/C++数据结构,链表,c语言,c++,数据结构

函数设计:

  1. 在每个节点后面复制一个一模一样的copy节点
  2. copy->random = cur->random->next
  3. 将copy部分和原节点断开
struct Node* copyRandomList(struct Node* head) 
{
    //1. 在每个节点后面复制一个相同的节点
    struct Node* cur = head;
    if (cur == NULL) 
        return NULL;
    while (cur) 
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
 
    //2. copy->random = cur->random->next
    cur = head;
    while (cur) 
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL) 
            copy->random = NULL;
        else 
            copy->random = cur->random->next;
        cur = copy->next;
    }
 
    //3. 将copy部分和原链表断开
    cur = head;
    struct Node* copy = cur->next;
    struct Node* copytail = copy;
    while (cur) 
    {
        struct Node* next = copytail->next;
        cur->next = next;
        if (next) 
            copytail->next = next->next;
        cur = next;
        copytail = copytail->next;
    }
 
    return copy;
}

到了这里,关于【C/C++数据结构】链表与快慢指针的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法初阶(C语言)】复杂链表(随机指针,随机链表的复制)题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题: 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(83)
  • 【数据结构与算法分析】反转链表与顺序表(内含源码,思路清晰)

      顺序表和链表都是数据结构中常见的线性表。它们的主要区别在于 内存管理方式不同 。   顺序表(Array)是由一系列元素按照一定顺序依次排列而成,它使用连续的内存空间存储数据。顺序表使用一个数组来存储数据,数组中的每个元素都可以通过下标来访问。顺序

    2024年02月07日
    浏览(103)
  • 数据结构三叉链表与线索二叉树的思路与实现详解

    ❤️作者主页:微凉秋意 ✅作者简介:后端领域优质创作者🏆,CSDN内容合伙人🏆,阿里云专家博主🏆 我们知道最常见的链式存储二叉树的结构体中有数据域、左孩子指针以及右孩子指针,通过递归来创建二叉树。显而易见的是,想找到二叉树中任意一个结点的 前驱 或 后

    2024年02月02日
    浏览(56)
  • [Collection与数据结构] 链表与LinkedList (一):链表概述与单向无头非循环链表实现

    上篇文章我们已经对顺序表进行了实现,并且对ArrayList进行了使用,我们知道ArrayList底层是使用数组实现的. 由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时, 就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低 ,因此ArrayList不适合做

    2024年04月26日
    浏览(62)
  • 【数据结构与算法】之8道顺序表与链表典型编程题心决!

                                                                                    个人主页:秋风起,再归来~                                                                                             数据结构与算

    2024年04月14日
    浏览(54)
  • 【数据结构与算法】顺序表与链表(单链表和双链表)超详解图示与源码。

                                                       大家好,今天我们来学习数据结构中的顺序表与链表!源码在最后附上 首先我们先来认识一下 顺序表 :                                       **如上图所示:很多人会以为数组就是顺序表,顺序表就是数组,这

    2024年02月21日
    浏览(55)
  • LeetCode - 142. 环形链表 II (C语言,快慢指针,配图)

            如果你对快慢指针,环形链表有疑问,可以参考下面这篇文章,了解什么是环形链表后,再做这道题会非常简单,也更容易理解下面的图片公式等。 LeetCode - 141. 环形链表 (C语言,快慢指针,配图)-CSDN博客         上述文章总结: 如果一个链表是环形链表,采用

    2024年02月05日
    浏览(55)
  • 【数据结构】两两交换链表 && 复制带随机指针的链表

    给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 使用一个栈S来存储相邻两个节点即可 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以

    2024年04月15日
    浏览(49)
  • 数据结构与算法----复习Part 8 (链表双指针)

    本系列是算法通关手册LeeCode的学习笔记 算法通关手册(LeetCode) | 算法通关手册(LeetCode) (itcharge.cn) 本系列为自用笔记,如有版权问题,请私聊我删除。 目录 一,双指针简介(Two Pointers) 二,起点不一致的快慢指针 三,步长不一致的快慢指针 判断链表中是否含有环: 四

    2024年02月19日
    浏览(55)
  • 【数据结构】[LeetCode138. 复制带随机指针的链表]

    给你一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random  ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的  深拷贝 。 深拷贝应该正好由  n  个  全新  节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的  next  指针和

    2024年02月04日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包