首页 > 编程语言 >【数据结构】详细剖析链表，带你实现单链表，双向链表，附链表编程练习题

【数据结构】详细剖析链表，带你实现单链表，双向链表，附链表编程练习题

时间：2024-08-18 09:24:13浏览次数：11  
标签：练习题 单链 ListNode cur next 链表 节点 struct

目录

一. 链表

1. 链表的概念及结构

2. 单链表的实现

2.1 单链表节点结构

2.2 动态申请一个节点

2.3 单链表打印

2.4 单链表尾插

2.5 单链表头插

2.6 单链表尾删

2.7 单链表头删

2.8 单链表查找 

2.9 单链表在pos后一位插入x

2.10 单链表删除pos后一位的值

2.11 单链表销毁 

3. 链表的分类 

3.1 单向或双向

3.2 带头或不带头

3.3 循环或不循环

3.4 最常用 

4. 带头双向循环链表的实现

4.0 节点结构

4.1 创建节点

4.2 双向链表销毁

4.3 双向链表打印 

4.4 双向链表尾插

4.5 双向链表尾删

4.6 双向链表头插

4.7 双向链表头删

4.8 双向链表查找

4.9 双向链表在pos的前面进行插入

4.10 双向链表删除pos位置的节点

5. 链表编程练习题

5.1 移除链表元素

5.2 链表的中间结点

5.3 合并两个有序链表

5.4 反转链表 

5.5 链表分割

5.6 相交链表

5.7 环形链表 

5.8 环形链表返回环节点

5.9 随机链表的复制 

二. 顺序表和链表的区别 

一. 链表

1. 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

2. 单链表的实现

2.1 单链表节点结构

1. 使用typedef重命名数据类型是为了方便类型的更改。

2. 结构包含存放的数据和指向下一个节点的地址。

typedef int SLDataType;
typedef struct SingleListNode
{
	SLDataType data;
	struct SingleListNode* next;
}SLNode;

2.2 动态申请一个节点

1. 使用malloc申请一块节点空间。

2. 将节点内容初始化。 

SLNode* BuySLNode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

2.3 单链表打印

1. 通过获取下一个节点地址进行遍历并打印数据。

2. 遇到空节点停下。

void SLPrint(SLNode* plist)
{
	SLNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

2.4 单链表尾插

1. pplist不可能为空，所以加断言。

2. 无节点情况：直接将新节点地址给头指针。

3. 有节点情况：将最后一个节点连接新节点。

void SLPushBack(SLNode** pplist, SLDataType x)
{
	assert(pplist);

	SLNode* newnode = BuySLNode(x);
	if (*pplist == NULL) *pplist = newnode; //无节点
	else                                    //有节点
	{
		SLNode* cur = *pplist;
		while (cur->next != NULL) cur = cur->next;
		cur->next = newnode;
	}
}

2.5 单链表头插

1. 先将新节点连接第一个结点，再将头指针连接新节点。   

void SLPushFront(SLNode** pplist, SLDataType x)
{
	assert(pplist);

	SLNode* newnode = BuySLNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

2.6 单链表尾删

1. 单节点情况：释放节点然后置空。

2. 多节点情况：利用倒数第二个节点，释放倒数第一个节点并置空。

void SLPopBack(SLNode** pplist)
{
	assert(pplist && *pplist);

	SLNode* cur = *pplist;
	if (cur->next == NULL) //单节点
	{
		free(cur);
		*pplist = NULL;
	}
	else                   //多节点
	{
		while (cur->next->next != NULL) cur = cur->next;
		free(cur->next);
		cur->next = NULL;
	}
}

2.7 单链表头删

1. *pplist不能为空，因为空节点不用删。

2. 将头指针指向第二个节点，释放第一个节点。

void SLPopFront(SLNode** pplist)
{
	assert(pplist && *pplist);

	SLNode* del = *pplist;
	*pplist = del->next;
	free(del);
}

2.8 单链表查找 

1. 遍历一遍，比较数据。

SLNode* SLFind(SLNode* plist, SLDataType x)
{
	SLNode* cur = plist;
	while (cur)
	{
		if (cur->data == x) return cur;
		cur = cur->next;
	}

	return NULL;
}

2.9 单链表在pos后一位插入x

1. 先将新节点连接pos的后一个节点，再将pos连接新节点。

void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);

	SLNode* newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2.10 单链表删除pos后一位的值

1. 空节点不用删。

2. 将pos和pos后面第二个节点连接，释放pos后面第一个节点。

void SLEraseAfter(SLNode* pos)
{
	assert(pos);

	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

2.11 单链表销毁 

1. 遍历链表释放每个节点。

void SLDestroy(SLNode** pplist)
{
	assert(pplist);

	while (*pplist)
	{
		SLNode* cur = *pplist;
		*pplist = (*pplist)->next;
		free(cur);
	}
}

完整代码： SingleList/SingleList · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)

3. 链表的分类 

链表可以分三类，这三类组合起来一共有8种结构。

3.1 单向或双向

3.2 带头或不带头

3.3 循环或不循环

3.4 最常用 

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

4. 带头双向循环链表的实现

4.0 节点结构

1. 两个指针，指向前面和后面。

typedef int ListDataType;
typedef struct ListNode
{
	ListDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

4.1 创建节点

1. 这里可以创建哨兵位节点，也可以是其他新节点。

2. 通过malloc申请一块节点空间，将两个指针指向自己。

ListNode* ListCreate()
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	if (head == NULL)
	{
		perror("malloc");
		return NULL;
	}
	head->prev = head;
	head->next = head;

	return head;
}

4.2 双向链表销毁

1. 先获取有效节点也就是哨兵位下一个节点，遍历释放空间，直到循环遇到哨兵位停下。

2. 最后把哨兵位也释放。

void ListDestory(ListNode* plist)
{
	assert(plist);

	ListNode* cur = plist->next;
	while (cur != plist)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(plist);
}

4.3 双向链表打印 

1. 获取哨兵位的下一个节点，遍历打印，直到循环遇到哨兵位停下。

void ListPrint(ListNode* plist)
{
	assert(plist);

	ListNode* cur = plist->next;
	printf("head<==>");
	while (cur != plist)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("head\n");
}

4.4 双向链表尾插

1. 获取最后一个节点，将新节点和最后一个节点连接，再将新节点和哨兵位连接。

void ListPushBack(ListNode* plist, ListDataType x)
{
	assert(plist);

	ListNode* newnode = ListCreate();
	newnode->data = x;

	ListNode* tail = plist->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = plist;
	plist->prev = newnode;
}

4.5 双向链表尾删

1. 只有哨兵位时不允许删。

2. 获取最后一个节点和倒数第二个节点，将倒数第二个节点和哨兵位连接，释放最后一个节点。

void ListPopBack(ListNode* plist)
{
	assert(plist);
	assert(plist->next);

	ListNode* tail = plist->prev;
	ListNode* prev = tail->prev;
	prev->next = plist;
	plist->prev = prev;
	free(tail);
}

4.6 双向链表头插

1. 获取哨兵位的下一个节点，新节点和哨兵位连接，新节点再和哨兵位的下一个节点连接。

void ListPushFront(ListNode* plist, ListDataType x)
{
	assert(plist);

	ListNode* newnode = ListCreate();
	newnode->data = x;

	ListNode* cur = plist->next;
	plist->next = newnode;
	newnode->prev = plist;
	newnode->next = cur;
	cur->prev = newnode;
}

4.7 双向链表头删

1. 只有哨兵位时不允许删。

2. 获取第一个有效节点和第二个有效节点，将哨兵位与第二个有效节点连接，释放第一个有效节点。

void ListPopFront(ListNode* plist)
{
	assert(plist && plist->next);

	ListNode* cur = plist->next;
	ListNode* next = cur->next;
	plist->next = next;
	next->prev = plist;
	free(cur);
}

4.8 双向链表查找

1. 遍历有效节点，比较数据。

ListNode* ListFind(ListNode* plist, ListDataType x)
{
	assert(plist);

	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x) return cur;
		cur = cur->next;
	}
	return NULL;
}

4.9 双向链表在pos的前面进行插入

1. 先获取pos前面的节点，将新节点与pos前面的节点连接，然后新节点再与pos连接。

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);

	ListNode* newnode = ListCreate();
	newnode->data = x;

	ListNode* prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

4.10 双向链表删除pos位置的节点

1. 获取pos的前后节点，将他们连接，释放pos节点。

void ListErase(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

完整代码：List/List · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)

5. 链表编程练习题

5.1 移除链表元素

链接：. - 力扣（LeetCode）

思路：

1. 遍历链表，删除相同值得节点。

2. 使用前后指针，方便节点的释放。

3. 注意特殊情况，当第一个节点就需要删除的时候。

struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    while(cur)
    {
        if(cur->val == val)
        {   
            if(prev == NULL) //这里判断的是当前是不是第一个节点，
            {                   //注意，删除完第一个节点后，第二个节点会变成新的第一个节点。
                cur = cur->next;
                free(head);
                head = cur;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }

    return head;
}

5.2 链表的中间结点

链接：. - 力扣（LeetCode）

思路：

1. 快慢指针，slow一次走一步，fast一次走两步。

2. 有奇数节点，偶数节点两种情况，奇数节点时fast走到最后一个节点停下，偶数节点时fast走到空停下。

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

5.3 合并两个有序链表

链接：. - 力扣（LeetCode）

思路：

1. 将小于或等于的节点尾插到一个新的指针上，返回这个指针。

2. 注意第一个节点尾插需要特殊处理。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if(list1 == NULL) return list2;
    if(list2 == NULL) return list1;

    struct ListNode* list3 = NULL;
    struct ListNode* cur = NULL;
    while(list1 && list2)
    {
        if(list1->val <= list2->val)
        {
            if(list3 == NULL) list3 = cur = list1;
            else
            {
                cur->next = list1;
                cur = cur->next;
            }
            list1 = list1->next;
        }
        else
        {
            if(list3 == NULL) list3 = cur = list2;
            else
            {
                cur->next = list2;
                cur = cur->next;
            }

            list2 = list2->next;
        }
    }

    if(list1) cur->next = list1;
    if(list2) cur->next = list2;

    return list3;
}

5.4 反转链表 

链接：. - 力扣（LeetCode）

思路1：用三个指针来实现反转。

struct ListNode* reverseList(struct ListNode* head) 
{
    if(head == NULL) return NULL;

    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3) n3 = n3->next;
    }

    return n1;
}

思路2：头插法，每次cur节点对rhead进行头插。

struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* rhead = NULL;
    struct ListNode* cur = head;
    
    while(cur)
    {
        struct ListNode* next = cur->next;

        cur->next = rhead;
        rhead = cur;

        cur = next;
    }

    return rhead;
}

5.5 链表分割

链接：链表分割_牛客题霸_牛客网

思路：

1. 分两个链表，将小于x的尾插一个链表，大于等于x的尾插另一个链表，最后连接起来。

2. 建议用带哨兵位的链表。

3. 连接起来后第二个链表最后记得指向NULL。

ListNode* partition(ListNode* pHead, int x) 
    {
        ListNode* h1 = (ListNode*)malloc(sizeof(ListNode));
        ListNode* h2 = (ListNode*)malloc(sizeof(ListNode));
        ListNode* h1tail = h1;
        ListNode* h2tail = h2;

        ListNode* cur = pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                h1tail->next = cur;
                h1tail = h1tail->next;
            }
            else 
            { 
                h2tail->next = cur;
                h2tail = h2tail->next;
            }

            cur = cur->next;
        }

        h1tail->next = h2->next;
        h2tail->next = NULL;
        pHead = h1->next;
        free(h1);
        free(h2);

        return pHead;
    }

5.6 相交链表

链接：. - 力扣（LeetCode）

思路：

1. 先求两个链表的长度。

2. 长的链表头指针先走，走到和短的链表一样长。

3. 两个指针一起走，直到遇到一样的节点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    int lenA = 0;
    int lenB = 0;
    struct ListNode* cur = headA;
    while(cur)
    {
        lenA++;
        cur = cur->next;
    }
    cur = headB;
    while(cur)
    {
        lenB++;
        cur = cur->next;
    }

    int gap = abs(lenA-lenB);
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if(lenA < lenB)
    {
        longlist = headB;        
        shortlist = headA;  
    }
    while(gap--) longlist = longlist->next;  

    while(longlist != shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
        
    return longlist;
}

5.7 环形链表 

链接：. - 力扣（LeetCode）

思路：

1. 利用快慢指针，如果有环那么会相遇，如果没环就走到链表结束。

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

    return false;
}

面试问题：

1. 快指针走两步，慢指针走一步，快指针和慢指针一定会相遇吗？

答：一定会，当他们进入环后，距离不断减1直到0。

快指针走n步，慢指针走一步，假设快指针追到慢指针的距离为N，那么N必须是n-1的倍数才能追上。错过之后，N也会发生变化重新计算。

5.8 环形链表返回环节点

链接：. - 力扣（LeetCode）

思路：

1. 结论：设头节点到入环点的距离为L，入环点到相遇点的距离为X，环的长度为C，

那么有：L = n*C - X，其中n为圈数。

一个指针从头节点开始走，一个指针从相遇点开始走，他们会在入环点相遇。

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            //此时slow是相遇点
            while(head != slow)
            {
                head = head->next;
                slow = slow->next;
            }

            return head;
        } 
    }   

    return NULL;
}

思路2：

1. 将相遇点的下一个节点保存，然后从相遇点开始断开链表，就形成了两条链表。

2. 一条链表是以原本的，另一条是以相遇点的下一个节点为头节点，这两条链表的交点就是入环点。

5.9 随机链表的复制 

链接：. - 力扣（LeetCode）

思路：

1. 将每个节点拷贝一份并在各自节点后面插入。

2. 可得出拷贝的随机指针是源节点的随机指针的下一位。

3. 分开拷贝节点。

struct Node* copyRandomList(struct Node* head) 
{
    if(head == NULL) return NULL;

    struct Node* cur = head;
    while(cur)
    {
        struct Node* tail = cur->next;
        struct Node* new = (struct Node*)malloc(sizeof(struct Node));
        new->val = cur->val;
        cur->next = new;
        new->next = tail;
        cur = tail;
    }

    cur = head;
    while(cur)
    {
        struct Node* tail = cur->next;
        if(cur->random == NULL) tail->random = NULL;
        else tail->random = cur->random->next;
        cur = cur->next->next;
    }

    cur = head;
    struct Node* nwehead = (struct Node*)malloc(sizeof(struct Node));
    struct Node* ret = nwehead;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* tail = copy->next;
        ret->next = copy;
        cur->next = tail;
        cur = tail;
        ret = copy;
    }
    
    return nwehead->next;
}

 

二. 顺序表和链表的区别 

1. 链表可以任意位置插入删除，顺序表适合尾插尾删。

2. 链表按需申请释放空间，顺序表是扩容空间，可能会浪费。

3. 顺序表支持下标随机访问，链表不支持。

标签：练习题,单链,ListNode,cur,next,链表,节点,struct
From： https://blog.csdn.net/m0_71164215/article/details/141165513

相关文章

  • 知识改变命运 数据结构【链表面试题】
    1.删除链表中等于给定值val的所有节点。OJ链接publicListNoderemoveElements(ListNodehead,intval){if(head==null){returnnull;}ListNodecur=head.next;ListNodepre=head;while(cur!=null){......
  • 数据结构----链表
    一丶概念     链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。      和顺序表不同同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。二丶特点     特点：内存不连续，通过指针进行连接 ......
  • 双向链表 尾节点插入
    importlombok.Data;publicclassT{publicstaticvoidmain(String[]args){DoubleLinkedListlist=newDoubleLinkedList();list.addTail(1);list.addTail(2);list.addTail(3);System.out.println("......
  • 数据结构中的双向链表
    1.链表的分类链表的结构非常多样，以下情况组合起来就是8种（2x2x2）链表结构：  在带头链表中，除了头结点，其他结点均存储有效的数据。头结点是占位子的，也叫做“哨兵位”。head结点就是头结点。 循环的链表尾结点不为NULL，不循环的链表尾结点为NULL单链表：不带头单向不循环链......
  • 代码随想录day3 | LeetCode203. 移除链表元素、LeetCode707. 设计链表、LeetCode206.
    代码随想录day3|LeetCode203.移除链表元素、LeetCode707.设计链表、LeetCode206.反转链表为了防止早上写博客上传图片失败，今天试试下午写，发现图片上传正常链表基础文章链接：链表基础C/C++的定义链表节点方式，如下所示：//单链表structListNode{intval;/......
  • 合并K个升序链表-力扣
    /***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx):val(x),next(nullptr){}*ListNode(intx,ListNode*next):val(x),next(ne......
  • 链表多选题（1）链表
    描述在一个链表中，已知p是指向结点c的指针变量，q是指向结点d的指针变量，s是指向结点h的指针变量，若在p和q之间插入结点s，则执行（） 输入描述无输出描述如果选择A选项，输出按照下面方法输出:示例#include<iostream>usingnamespacestd;intmain(){cout<<"AB";......
  • 【408DS算法题】016基础-倒序输出单链表的结点值
    Index题目分析实现总结题目给定单链表的头结点，倒序输出单链表的结点值。分析实现要倒序输出链表结点值，首先可以想到的是先将链表的结点值存储到数组中，然后利用数组随机访问的特性进行倒序输出。如果考虑其它思路的话，还可以使用栈来代替数组——将链表元素依次......
  • 链表中环的检测与入口节点的查找：哈希表与快慢指针方法
    前言在数据结构中，链表是一种常见的线性数据结构。链表中的环问题是面试和实际编程中经常遇到的一个问题。本文将先复习哈希表的基本概念，然后介绍两种检测链表中环的方法：哈希表法和快慢指针法，并分析它们的优缺点、原理以及时间和空间复杂度。哈希表复习定义：哈希表，又称散列表，......
  • Python合并两个有序链表
    题目合并两个有序链表，如l1=[1,3,4],l2=[1,2,4,5]，合并后l3=[1,1,2,3,4,4,5]解决思路需要构建节点Node和链表LinkedList结构如果root节点不确定，可以创建一个哑节点Node(0)，作为root节点的前节点，也是初始节点(当前节点)循环当l1当前节点不为None并且l2当前节点不为None时，那个节......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99