【数据结构】链表进阶_如何调用链表两次

目录

链表的分类

链表种类的基本概述

带头双向循环列表程序的实现

带头双向循环列表的基本概述

List.h

List.c

Test.c

链表oj练习题

反转链表

链表的中间节点 

合并两个有序链表

环形链表I

环形链表II

---

链表的分类

链表种类的基本概述

链表可以由上图所示，组合成八种不同结构的链表类型

双向链表

 带头链表

 循环链表

带头双向循环列表程序的实现

带头双向循环列表的基本概述

带头：指针直接指向一个哨兵位的头节点       

好处：增删查改操作中，不需要改变头节点的值，所以不需要使用二级指针

双向：在每一个节点中，存放了两个指针，一个指向前一个节点，另一个指向后一个节点

好处：在插入删除操作中，不要再次遍历链表，降低时间复杂度

循环：链表的最后一个节点的next指针指向头节点，第一个节点的prev指针指向的是尾节点

好处：不需要通过遍历的手段寻找尾节点了。

List.h

结构体是链表的最小单元，在带头双向循环列表中，定义一个结构体，主要包含三个部分：存储的数据，前一个节点的指针，后一个节点的指针。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
 
typedef int LTDataType;
typedef struct ListNode ListNode;
 
struct ListNode
{
	ListNode* prev;
	ListNode* next;
	LTDataType data;
};
 
void ListInit(ListNode** phead);
void ListDestory(ListNode* phead);
void ListPushBack(ListNode* phead, LTDataType x);
void ListPushFront(ListNode* phead, LTDataType x);
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);
void ListPrint(ListNode* phead);
ListNode* ListFind(ListNode* phead, LTDataType x);
void ListInsert(ListNode* phead, ListNode* pos, LTDataType x);
void ListErase(ListNode* phead, ListNode* pos);
struct ListNode* middleNode(struct ListNode* head);

List.c

各个函数的实现

ListInit

因为是带头的双向循环链表，先新建一个节点，再将prev和nex分别指向自己

void ListInit(ListNode* phead)
{
	//建立一个头节点
	//prev 和 next均指向phead
	//注意：这里改变了phead，也就是实参的值，所以需要二级指针
	phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
 
}

 这里我们运行程序，会发现

在plist中，仍然是<无法读取内存>，原因很简单，在该函数内，我们又试图改变传入的参数phead的值，但是形参无法改变实参，所以在这我们还需要使用二级指针。

void ListInit(ListNode** pphead)
{
	//建立一个头节点
	//prev 和 next均指向phead
	//注意：这里改变了phead，也就是实参的值，所以需要二级指针
	*pphead = BuyListNode(0);
	(* pphead)->next = *pphead;
	(* pphead)->prev = *pphead;
 
}

修改后我们可以十分清晰地看到初始化后链表的物理结构

 plist，也就是我们链表的头指针，其中prev和next又分别指向了自己

ListPushBack&ListPushFront

单链表中的尾插：需要分两种情况，当单链表为空时，需要将newnode赋给头节点；当单链表中有节点时，需要找到链表中最后一个节点，将newnode与其链接

双向循环链表：第一个节点的prev指向的就是最后一个节点！

所以可以非常轻松的找到最后一个节点

同样地：头插就更加简单，phead的下一个节点就是第一个节点（能够存储有效数字的第一个节点）

由此我们可以看出双向链表的优势所在。

void ListPushBack(ListNode* phead, LTDataType x)
{
	//断言：如果phead=NULL，则报错
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	//找到链表中最后一个节点
	ListNode* tail = phead->prev;
	//将newnode和头尾相连
	newnode->prev = tail;
	tail->next = newnode;
	newnode->next = phead;
	phead->prev = newnode;
	
}
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* first = phead->next;
	newnode->next = first;
	first->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
	
}

ListPopback&ListPopFront

头删尾删与上面操作基本一致，需要注意的是，是否链表中只含有带有哨兵位的头节点了，所以需要断言判断。不要将链表整个的结构全部删除了。

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* last = phead->prev;
	ListNode* last_but_two = last->prev;
	last_but_two->next = phead;
	phead->prev = last_but_two;
	free(last);
	last = NULL;
}
void ListPopFront(ListNode* phead)
{
	assert(phead);
	//检查传入的链表是否已经初始化
	assert(phead->next != phead);
	//检查链表是否只有一个哨兵位的节点
	ListNode* first = phead->next;
	ListNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}

ListInsert

void ListInsert(ListNode* phead, ListNode* pos, LTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* cur = pos->prev;
	cur->next = newnode;
	newnode->prev = cur;
	newnode->next = pos;
	pos->prev = newnode;
}

ListErase 

void ListErase(ListNode* phead, ListNode* pos)
{
	assert(phead);
	ListNode* front = pos->prev;
	ListNode* back = pos->next;
	front->next = back;
	back->prev = front;
	free(pos);
	pos = NULL;
 
}

ListPrint 

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

 ListFind

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

ListDesStory

 销毁链表的操作时，我们由之前的知识可知，链表是的最小单元是一个结构体，而结构体就是我们malloc而来的，所以我们需要先将所有节点销毁，再将整个结构，也就是头节点销毁。

值得注意的是，在遍历的过程中，free(cur)后，则会丢失对cur节点后的链表，所以需要先将cur->next进行保存，再将cur释放。

void ListErase(ListNode* phead, ListNode* pos)
{
	assert(phead);
	ListNode* front = pos->prev;
	ListNode* back = pos->next;
	front->next = back;
	back->prev = front;
	free(pos);
	pos = NULL;
 
}

Test.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
 
void TestList1()
{
	ListNode* plist = NULL;
	ListInit(&plist);
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushFront(plist, 0);
	ListPrint(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopBack(plist);
	ListPrint(plist);
	//ListDestory(plist);
	ListNode* pos = ListFind(plist,3);
	if (pos == NULL)
	{
		printf("查无此值\n");
	}
	else
	{
		printf("%p\n", pos);
	}
	pos = ListFind(plist, 3);
	if (pos == NULL)
	{
		printf("插入失败\n");
	}
	else
	{
		ListInsert(plist, pos, 10);
	}
	ListPrint(plist);
	pos = ListFind(plist, 3);
	if (pos == NULL)
	{
		printf("删除失败\n");
	}
	else
	{
		ListErase(plist, pos);
	}
	ListPrint(plist);
	ListDestory(plist);
}
 
int main()
{
	TestList1();
	return 0;
}

这里给出的是一个测试函数，在我们写程序的同时，我们应该写一点测一点，避免出现错误多到溢出的情况。

也可以写一个主菜单，实现链表的多个功能。

详情可参考

10.27单链表_zhangyuaizhuzhu的博客-CSDN博客

链表oj练习题

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

 

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list

 思路一：翻指针

注意！！！数据结构题目合理利用图表可以帮助我们更快的找到思路，解决问题

一般来说，解决一个需要重复完成的问题，通常需要三个步骤：

1.初始条件 2.迭代条件 3.结束条件

对于本道题而言，要实现链表的反转，自然而然地会想到双向链表，但是题目仅仅给了我们单链表，所以我们不难想到，可以倒转指针的指向，返回最后一个节点的指针。

 1.初始条件：我们定义三个结构体指针n1,n2,n3（保存n2后面的链表）,其中n1指向空，n2指向第一个节点，n3指向第二个节点 

2.迭代过程：将原本n2指向n3的指针反转，指向n1。（将原本指向后一个节点的指针指向前一个节点）这步操作的目的是将整个链表翻转。

再将n1，n2，n3整体向后移位。这步操作的目的是进行迭代

一个循环体的基本操作有

1.改变指针指向

2.移位

每次循环，都将会进行一次完完整整的循环体

如此反复

 3.结束条件：由图可知，当n2指向NULL时，已经达到翻转的效果，所以，结束的条件为：

n2 ==NULL

struct ListNode* reverseList(struct ListNode* head){
    //head为空的特殊条件
    if (head == NULL)
    {
        return head;
    }
    //初始条件
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;
    //结束条件
    while (n2 != NULL)
    {
        //迭代过程
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        //n3有可能为空，则空指针的next会出问题
        if (n3 == NULL)
        {
            n3 = NULL;
        }
        else
        {
             n3 = n3->next;
        }
    }
    return n1;
}

思路二：头插法

新建一个链表newhead，将head从前往后遍历，将head中的节点依次头插到newhead中

1.初始条件：cur = head（用于遍历原链表） newhead（新链表）next（保存cur后面的节点）

2.迭代过程：完成我们想要的操作后，要将其他变量还原为开始迭代前的状态

将cur指向的节点头插入newhead中——我们想要的操作

newhead向前移动位置——还原操作

将cur和next向后移动位置——还原操作

3.结束条件：cur为空时即结束

struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = cur->next;
    while (cur != NULL)
    {
        cur->next = newhead;
        newhead = cur;
        cur = next;
        if (next)
        {
            next = next->next;
        }
    }
    return newhead;
}

链表的中间节点 

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
 

提示：

给定链表的结点数介于 1 和 100 之间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/middle-of-the-linked-list

方法一：遍历两次链表

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* cur = head;
    int count = 1;
    while (cur->next != NULL)
    {
        cur = cur->next;
        count++;
    }
    cur = head;
    int i = 1;
    while (i < count / 2 + 1)
        {
            cur = cur->next;
            i++;
        }
    return cur;
 
}

遍历第一次，求得链表的长度

遍历第二次找到中间节点

方法二：只遍历一次链表，快慢指针法

核心：慢指针走一步，快指针走两步

奇数偶数节点要分情况考虑

当有奇数个节点时

此时，slow指向中间，fast指向的是最后一个节点

当有偶数个节点时

此时，slow指向中间，fast指向NULL

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

注意：循环结束的条件是fast指向空或者fast->next指向空

           则循环继续的条件是fast和fast->next不指向空

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
 

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-sorted-lists

思路：找两个链表中值最小的进行尾插

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL)
    {
        return list2;
    }
    else if (list2 ==NULL)
    {
        return list1;
    }
    else
    {
        struct ListNode* head = NULL;
        struct ListNode* tail = NULL;
        while (list1 != NULL && list2 != NULL)
        {
            if (list1->val >= list2->val)
            {
                if (tail == NULL)
                {
                    head = tail = list2;
                }
                else 
                {
                    tail->next = list2;
                    tail = tail->next;
                }
                list2 = list2->next;
            }
            else
            {
                if (tail == NULL)
                {
                    head = tail = list1;
                }
                else 
                {
                    tail->next = list1;
                    tail = tail->next;
                }
                list1 = list1->next;
            }
        }
        if (list1 != NULL)
        {
            tail->next = list1;
        }
        else
        {
            tail->next = list2;
        }
        return head;
    }
}   

有几个需要注意的点：
1.边界条件：list1或list2为空时，返回另一个链表

2.为什么要定义head和tail：

head：题目要求head作为头节点返回

tail：进行尾插时，如果没有tail，则需要多次遍历，徒增时间。不如定义一个tail指向最后一个节点

3.在尾插时，一定要注意tail是否为空，如果为空，则tail->next会报错，所以需要提前判断。

4.循环结束后，可能会出现的结果是，有一个链表没有值了，另一个链表还有节点，此时则需要直接将剩下的链表全部尾插即可。

由于判断tail是否为空，所以程序会出现冗余，下面提供两种方式优化代码

第一：在循环前就将head和tail先进行一次尾插

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL)
    {
        return list2;
    }
    else if (list2 ==NULL)
    {
        return list1;
    }
    else
    {
        struct ListNode* head = NULL;
        struct ListNode* tail = NULL;
        if (list1->val <= list2->val)
        {
            head = tail = list1;
            list1 = list1->next;
        }
        else
        {
            head = tail = list2;
            list2 = list2->next;
        }
        while (list1 != NULL && list2 != NULL)
        {
            if (list1->val >= list2->val)
            {
                tail->next = list2;
                list2 = list2->next;
            }
            else
            {
                tail->next = list1;
                list1 = list1->next;
            }
            tail = tail->next;
        }
        if (list1)
        {
            tail->next = list1;
        }
        else
        {
            tail->next = list2;
        }
        return head;
    }
}   

第二：将单链表改成带头结点的链表，返回时只需返回head->next即可

malloc一个带有哨兵位的头节点，防止tail为空时，出现编译错误

最后注意，应当返回head->next

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL)
    {
        return list2;
    }
    else if (list2 ==NULL)
    {
        return list1;
    }
    else
    {
        struct ListNode* head = NULL;
        struct ListNode* tail = NULL;
        //插入一个带哨兵位的头节点：如果防止tail为空时，tail->next出现编译错误
        head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
        while (list1 != NULL && list2 != NULL)
        {
            if (list1->val >= list2->val)
            {
                tail->next = list2;
                list2 = list2->next;
            }
            else
            {
                tail->next = list1;
                list1 = list1->next;
            }
            tail = tail->next;
        }
        if (list1)
        {
            tail->next = list1;
        }
        else
        {
            tail->next = list2;
        }
        //头节点不保存有效数据，所以应该返回头节点后，下一个节点
        return head->next;
    }

环形链表I

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
 

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
 

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

快慢指针法

定义一个快指针fast和一个慢指针slow，

1.如果fast或者fast->next为空时，则没有环

2.如果fast和slow相遇时（相等），则有环

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

思考：

slow = slow->next时，fast = fast->next->next就一定能相遇吗？

如果是fast = fast->next->next->next呢？

提示：

和快慢指针的间距N和环的长度C有关

环形链表II

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
 

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
 

进阶：你是否可以使用 O(1) 空间解决此题？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle-ii

思路：追击相遇问题

如同，若fast速度为slow的两倍

如果有环形链表，则此时fast先进入环

 当slow进入环内时，fast如图

当slow遍历的节点 < C 时，fast必会追上slow，定义相遇的节点为meet。

则slow遍历的节点为 Y + L，fast遍历的节点为 Y + N * C + L

则可列写方程

L + Y + N * C = 2 * （Y + L）

则 Y + L = N * C

∴ L = C - Y + （N - 1）* C

这里我们得到了一个很重要的结论：

从头节点开始遍历与从meet节点开始遍历的两个指针，肯定会在进环起点相遇

struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode *fast = head, *slow = head;
    struct ListNode *meet = NULL;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            meet = fast;
            while (meet != head)
            {
                head = head->next;
                meet = meet->next;
            }
            return head;
        }
    }
    return NULL;
}