【数据结构】线性表——链表

写在前面

本篇笔记记录线性表——链表的主要形式，虽然链表有8种形式，但是只要精通笔记中编写的两种，即可触类旁通。

---

文章目录

• 写在前面
• 一、链表的概念及结构
• 二、链表的分类
• 三、无头单向非循环链表
• • 3.1、链表的实现
  • • 3.1.1、链表的结构体定义
    • 3.1.2、动态申请一个节点
    • 3.1.3、单链表打印
    • 3.1.4、单链表尾插
    • 3.1.5、单链表的头插
    • 3.1.6、单链表的尾删
    • 3.1.7、单链表头删
    • 3.1.8、单链表查找
    • 3.1.9、单链表在pos位置之后插入x
    • 3.1.10、单链表删除pos位置之后的值
    • 3.1.11、链表的销毁
    • 3.1.12、单链表在pos的前面插入
    • 3.1.13、删除pos位置
  • 3.2、OJ练习
  • • 3.2.1、反转链表
    • 3.2.2、相交链表
    • 3.2.3、 环形链表 II
    • 3.2.4、随机链表的复制
• 四、带头双向循环链表
• • 4.1、带头+双向+循环链表的实现
  • • 4.1.1、链表的结构体定义
    • 4.1.2、创建返回链表的头结点.
    • 4.1.3、双向链表销毁
    • 4.1.4、双向链表打印
    • 4.1.5、 双向链表尾插
    • 4.1.6、双向链表尾删
    • 4.1.7、双向链表头插
    • 4.1.8、双向链表头删
    • 4.1.9、双向链表查找
    • 4.1.10、双向链表在pos的前面进行插入
    • 4.1.11、双向链表删除pos位置的节点
  • 4.2、优化带头双向循环链表的实现
  • • 4.2.1、优化后的双向链表尾插
    • 4.2.2、优化后的双向链表尾删
    • 4.2.3、优化后的双向链表头插
    • 4.2.4、优化后的双向链表头删
• 5.顺序表和链表的区别

---

一、链表的概念及结构

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

逻辑结构是程序猿们为了更直观的理解而画出来的结构。在真实的内存存储中并无这样。

二、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

一、单向或者双向

二、带头或者不带头（有无哨兵位）

三、循环或者非循环

在上面介绍的三大类中，相互结合可以得到 2³ 种结合方式。

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

• 无头单向非循环链表
• 带头双向循环链表(在掌握后，可以20分钟内手撕出来)

---

三、无头单向非循环链表

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。又因为无法通过当前节点找到前节点的地址，所以这种结构在笔试面试考试中出现很多。只要是考察单链表的，就是考察这个。（如下图）

3.1、链表的实现

链表的实现：链表的命名规则借鉴c++中的stl库

3.1.1、链表的结构体定义

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

• typedef int SLTDateType;把链表结构的类型重命名为：SLTDateType。若将来如果要改变链表内容的结构类型，就可以极为方便的改变。
• 在结构体中定义了链表的存储的内容与存储下个节点的指针。
• 为了更方便使用链表结构体，把链表结构体重命名为SListNode。

3.1.2、动态申请一个节点

SListNode* BuySListNode(SLTDateType x) {
	SListNode* ma = (SListNode*)malloc(sizeof(SListNode));
	if (ma == NULL) {
		perror("malloc in BuySListNode::");
	}
	ma->data = x;
	ma->next = NULL;
	return ma;
}

• 因为我们要实现的是无头单向非循环链表，所以只有插入一个节点时候才会申请一个节点，所以我们就需要设置一个形参，用来接收插入的内容。
• 在申请一个节点时，我们不知道该节点需要存放在哪个位置，为了避免野指针，所以我们统一把next设为NULL，在调用BuySListNode之后，程序猿根据自己的需求来调整next指针。

3.1.3、单链表打印

void SListPrint(SListNode* plist) {
	printf("内容为:>");
	SListNode* p1 = plist;
	while (p1) {
		printf("%d => ", p1->data);
		p1 = p1->next;
	}
	printf("\n");
}

• 我们只需要循环遍历链表，把链表的值打印出来即可。
• 循环条件设置为指针，当指针为NULL时，证明链表已经结束，并且循环条件为NULL时判定为假，为假结束循环。

3.1.4、单链表尾插

void SListPushBack(SListNode** pplist, SLTDateType x) {
	SListNode* capacity = BuySListNode(x);
	SListNode* ptr1 = *pplist;

	if (*pplist == NULL) {
		*pplist = capacity;
	}
	else {
		while (ptr1->next != NULL) {
			ptr1 = ptr1->next;
		}
		ptr1->next = capacity;
	}
}

• 需要使用二级指针来接收链表的地址，因为只有二级指针才可以访问到链表的指针。只有链表的指针才可以依此访问链表的内容。（如下图）

• 把需要插入的x值传递给BuySListNode函数开辟一个节点。

• 在尾插之前，我们需要判断*pplist是否为NULL，如为NULL说明链表里面目前没有一个节点，那就需要把*pplist赋值为头的节点

• 判断了*pplist不为NULL，则循环查找，找到ptr1->next值为NULL即找到链表最后一个节点。

• 在找到链表最后一个节点后，把新开辟的节点的地址赋值给该节点的next值，即完成了链接。

3.1.5、单链表的头插

void SListPushFront(SListNode** pplist, SLTDateType x) {
	assert(pplist);
	SListNode* capacity = BuySListNode(x);
	if (pplist == NULL) {
		*pplist = capacity;
	}
	else {
		capacity->next = (*pplist);
		*pplist = capacity;
	}
}

• 把需要插入的x值传递给BuySListNode函数开辟一个节点。
• 在头插之前，我们需要判断*pplist是否为NULL，如为NULL说明链表里面目前没有一个节点，那就需要把*pplist赋值为头的节点
• 判断了*pplist不为NULL，则把新开辟的节点的next值存放*pplist，然后再把*pplist指向新开辟的节点，这样就完成头插了。

3.1.6、单链表的尾删

void SListPopBack(SListNode** pplist) {
	assert(*pplist);
	int i = 0;
	SListNode* prev = *pplist;
	SListNode* ptr1 = *pplist;
	if (ptr1->next == NULL) {
		free(ptr1);
		*pplist = NULL;
		return;
	}
	while(ptr1->next){
		prev = ptr1;
		ptr1 = ptr1->next;
	}
	prev->next = NULL;
	free(ptr1);	
}

• 先用断言assert判断链表是否是NULL，如果为空就报错。(你空的你还删什么????????)
• 因为单链表无法在当前节点找到上一个节点的位置，所以需要两个指针，一个记录当前节点(ptr1)，一个记录上一个节点(prev)
• 在删除节点前，我们需要判断一下当前链表是否只剩下一个节点，如果只剩下一个节点就直接free掉，把*pplist赋值为空即可。
• 如果链表还剩下不止一个节点时，我们就循环找到尾部，通过prev = ptr1;与ptr1 = ptr1->next;的搭配，可以把prev永远设为ptr1的上一个节点，把prev的next赋值为空，之后free掉尾节点完成尾删。
• prev = ptr1;与ptr1 = ptr1->next;的搭配：在第一次进入循环语句是，ptr1与prev是同一指向链表的头节点的，之后ptr1再指向下一个节点，这样就把ptr1变为了next节点，到最后ptr1->next为空时，不再进入循环，那此时ptr1就指向尾节点，prev还是指向ptr1的上一个节点。

3.1.7、单链表头删

void SListPopFront(SListNode** pplist) {
	assert(*pplist); 
	SListNode* Next = (*pplist)->next;
	free(*pplist);
	*pplist = Next;
}

• 先用断言assert判断链表是否是NULL，如果为空就报错。(你空的你还删什么????????)
• 创建一个Next指针指向当前节点的next节点，之后直接free掉*pplist就可以完成头节点的删除了，但是别忘记把Next赋值给*pplist指针，完成链表头节点的重定位。
• 在上述头删代码中， 如果只有一个节点的情况也是可以正常运行的，因为只有一个节点时，头节点的next值是NULL，在free掉头节点后，把Next赋值给*pplist指针，也是把*pplist定为了NULL。

3.1.8、单链表查找

SListNode* SListFind(SListNode* plist,const SLTDateType x) {
	assert(plist);

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

• 先用断言assert判断链表是否是NULL，如果为空就报错。(你空的你还找什么????????)
• 循环遍历即可。

3.1.9、单链表在pos位置之后插入x

如果在pos位置之前插入，要脑筋急转弯一下(我们后面实现在位置之前插入)

void SListInsertAfter(SListNode* pos, SLTDateType x) {
	assert(pos);
	SListNode* p1 = pos;
	SListNode* capacity = BuySListNode(x);
	capacity->next = p1->next;
	p1->next = capacity;
}

• 先用断言assert判断链表是否是NULL，如果为空就报错。(你空的哪有什么pos位置？????????)
• 把需要插入的x值传递给BuySListNode函数开辟一个节点。
• 把当前节点的next值赋值给新开辟的节点的next。这样不会丢失pos之后的链表（如下图）。
• 把capacity的next成功链接到pos节点后的链表后，我们再把pos节点的next值指向capacity。这样就完成在pos位置之后插入x（如下图）。

3.1.10、单链表删除pos位置之后的值

如果删除pos位置节点，需要脑筋急转弯一下(我们后面实现删除pos位置节点)

void SListEraseAfter(SListNode* pos) {
	assert(pos && pos->next);
	SListNode* Next = pos->next;
	pos->next = Next->next;
	free(Next);
}

• 先用断言assert判断链表头节点与头节点的下一个节点是否是NULL，如果为空就报错。(你都没有两个节点哪有什么pos之后位置？????????)
• 定义一个值记录pos的下一个节点，把pos节点的next值存放Next->next值后，就链接上了头节点的下一个节点的之后的链表(如下图)。
• 在连接成功后，我们就直接free掉Next即可完成删除pos位置之后的值。

3.1.11、链表的销毁

链表的销毁非常简单，遍历free即可。

void SLTDestroy(SListNode** pphead) {

	SListNode* p1 = (*pphead)->next;
	while (*pphead) {
		free(*pphead);
		*pphead = p1;
		if (*pphead != NULL) {
			p1 = (*pphead)->next;
		}
	}
}

• 注意的是，需提前记录要释放的节点的下一个节点。

3.1.12、单链表在pos的前面插入

void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x) {
	assert(*pphead);
	SListNode* prev = *pphead;
	while (prev->next != pos) {
		prev = prev->next;
	}
	SListNode* p1 = BuySListNode(x);
	p1->next = prev->next;
	prev->next = p1;
}

• 在经历了完成链表的实现后，我们再看上述代码就轻松多了。
• 只要把prev节点控制在pos节点前一个节点，我们就使用和尾插相同的逻辑就可以实现pos的前面插入

3.1.13、删除pos位置

void SLTErase(SListNode** pphead, SListNode* pos) {
	assert(*pphead);
	SListNode* prev = *pphead;
	while(prev->next != pos){
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
}

• 在经历了完成链表的实现后，我们再看上述代码就轻松多了。
• 只要把prev节点控制在pos节点前一个节点，再使用和尾删相同的逻辑就可以实现删除pos位置

3.2、OJ练习

为了更好的理解单链表，我们尝试几道OJ题。

---

3.2.1、反转链表

反转链表的连接(点我跳转)

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    
}

解析：

方法一：

• head指针肯定是指向链表头节点的，题目要求我们反转链表，我们可以新建一个空链表，然后使用头插即可完成该题。
• 但是很有局限性，这个方法的时间复杂度和空间复杂度都是O(n)

方法二：(推荐)

1. 我们定义三个指针，分别记录原链表中的当前节点、prev节点与Next节点，之后我们反转当前节点、prev节点指针的指向，这样就完成了链表的反转，反转后我们还保留了原链表中Next节点，在Next节点之后的链表是未进行反转的
2. 我们利用保留的Next节点，重新分配当前节点、prev节点与Next节点，循环操作，即可把链表实现时间复杂度O(n)和空间复杂度O(1)的反转链表

struct ListNode* reverseList(struct ListNode* head) {
    // 初始化新链表头（newHead），指针1（ptr1）指向原链表的头部，Next用于保存下一个节点
    struct ListNode *newHead = NULL, *ptr1 = head, *Next = NULL;

    // 遍历原链表，逐个反转节点的指向
    while (ptr1) {
        Next = ptr1->next;   // 暂存当前节点的下一个节点，避免丢失

        ptr1->next = newHead;  // 将当前节点的next指向newHead，反转指针

        newHead = ptr1;  // 更新newHead，指向当前节点（原链表中的节点变成了新链表的节点）

        ptr1 = Next;  // 移动ptr1指针，指向原链表的下一个节点
    }

    // 返回新的链表头（即原链表的尾部）
    return newHead;
}

• 在上面代码中prev被newHead所替代，ptr1代表的是当前的节点

• （head不为空的情况）在第一次进入循环时，我们先让Next节点记录原链表。确保反转后还可以正常进行。（如下图）

• 我们把第一个节点的next指向newHead，此时newHead为空（如下图），这样就成功反转头节点的指向。

• 接下来把newHead指向ptr1，保证ptr1回到原链表后在初始链表中newHead还是ptr1的上一个节点，完成利用保留的Next节点，重新分配ptr1节点(如下图)，就把当前节点ptr1成返回到未反转指针的链表中。

• 判断ptr1是否为NULL即可判断未反转的链表是否结束

• 循环操作，当然一上来肯定是先让Next节点记录原链表。确保反转后还可以正常进行。，把当前节点ptr1的next指向newHead，此时newHead为初始链表时ptr1的上一个节点（如下图），这样就成功反转头节点的指向。

• 接下来把newHead指向ptr1，保证ptr1回到原链表后在初始链表中newHead还是ptr1的上一个节点，完成利用保留的Next节点，重新分配ptr1节点(如下图)，就把当前节点ptr1成返回到未反转指针的链表中。

• 如此循环直到ptr1为NULL时，结束反转，此时我们就得到了反转后链表的头节点newHead(如下图)。

• （head为空的情况)，在head为空是，ptr1节点也为NULL不会进入循环，我们在赋初值时就把newHead赋值为NULL，此时我们直接返回newHead也是正确。

---

3.2.2、相交链表

反转链表的连接(点我跳转)

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。
示例 1：

注意，函数返回结果后，链表必须 保持其原始结构 。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’

示例代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
}

解析：

• 在题目图示中，可以看到图示代码中有三组链表，其中链表a与b相交点是链表c。
• 但是正常遍历比较判断是无法判断出相交点，因为a与b链表的长度不一。

解题方法：

1. 先求出两个数组的长度。
2. 之后求出长度差。
3. 把长度长的链表先运行长度差个节点。之后一起运行。确保两个链表从剩余长度相同的地方开始比较。
4. 在同时运行过程中，我们每次都判断节点的地址是否相同，若相同时，说明该节点相交。
5. 如果遍历完成仍没有找到交点，则返回NULL，说明两个链表没有交点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    // 如果其中一个链表为空，返回NULL（没有交点）
    if (headA == NULL || headB == NULL) {
        return NULL;
    }

    // 定义计数器i和j，分别用于记录链表A和链表B的长度
    int i = 0, j = 0;

    // 创建两个指针，分别指向链表A和链表B的头节点
    struct ListNode *newa = headA, *newb = headB;

    // 计算链表A的长度
    while (newa) {
        i++;               // 计数器i加1
        newa = newa->next; // 移动指针到下一个节点
    }

    // 计算链表B的长度
    while (newb) {
        j++;               // 计数器j加1
        newb = newb->next; // 移动指针到下一个节点
    }

    // 创建两个指针，分别指向链表A和链表B的头节点
    struct ListNode *pa = headA, *pb = headB;

    // 如果链表A比链表B长，先移动链表A的指针，使两个链表剩余部分长度相等
    if (i > j) {
        int num = i - j;  // 计算链表A比链表B长的差距
        while (num) {      // 移动链表A的指针，直到两个链表剩余部分长度相同
            pa = pa->next;
            num = num - 1; // 差距减少1
        }
    }
    // 如果链表B比链表A长，先移动链表B的指针，使两个链表剩余部分长度相等
    else if (j > i) {
        int num = j - i;  // 计算链表B比链表A长的差距
        while (num) {      // 移动链表B的指针，直到两个链表剩余部分长度相同
            pb = pb->next;
            num = num - 1; // 差距减少1
        }
    }

    // 现在，链表A和链表B的剩余部分长度相同，从头开始比较
    while (pa != NULL) {
        if (pa == pb) {  // 如果两个指针指向同一个节点，说明找到了交点
            return pa;    // 返回交点节点
        } else {          // 如果没有找到交点，继续向后移动
            pa = pa->next;
            pb = pb->next;
        }
    }

    // 如果遍历到末尾没有找到交点，返回NULL
    return NULL;
}

---

3.2.3、 环形链表 II

反转链表的连接(点我跳转)

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

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

不允许修改 链表。

示例 1：

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

解析：

• 此题主要考察的是在环中怎么找到环的起始点。
• 简化上图，我们在新画的图中寻找规律(如下图)
• 首先我们需要先使用快慢指针来判断这是否是一个有环的链表(快慢指针中：快指针为fast、慢指针为slow**。slow指针每次移动一步，fast指针每次移动两步。)
• 如果是有环链表快慢指针在环中一定会相交！(如下图) **
• 我们现在设 不是环的链表的长度为:L、环的周长为:C、入环点交点到快门指针交点长度为：N(如图)
• 根据上图中的标记，我们列出快指针和慢指针在相遇时的方程(在相遇前我们不知道快指针在环内转了多少圈，设转了X圈)：fast = L+X*C+ N；slow = L + N
• 根据快门指针的特性（快指针是慢指针的二倍)，我们可以得到如下公式：fast =2*slow。即： L+X*C+ N = 2 * ( L + N)。
• 我们逐步化简公式：(如下图)
• 因为我们要求入环点：观看图一(鼠标移动到图片有提示) 可以看到入环点是不是环的链表的长度L，即在L处相交就是入环点 。
• 据上图公式，为了求出长度L，只有在相交点处开始运行才比能在入环点处多走N步，多走N步后才能抵消-N带来的影响，那此时，我们上图的公式就变为了：L=X*C。又因为N是入环点到快慢指针的相交点的距离，说明找入环点指针的起始点必须在快慢指针的相交点才能求出入环点。
• 此时我们只需要定义一个指针在链表开头开始逐步往后运行，定义一个指针在快慢指针的相交点处开始逐步运行，两个指针相交的时刻即为链表的入环点。

解题方法：

1. 先求出找到快门指针的交点。
2. 之后分别定义两个指针，一个在链表开头开始逐步往后运行，一个指针在快慢指针的相交点处开始逐步运行。

struct ListNode* detectCycle(struct ListNode* head) {
    // 如果链表为空或只有一个节点（即没有环），直接返回NULL
    if (head == NULL || head->next == NULL) {
        return NULL;
    }

    // 定义快慢指针和辅助指针
    struct ListNode *slow, *fast, *ptr;

    // 初始化慢指针和快指针，都指向链表头
    slow = head;
    fast = head;

    // 使用快慢指针检测环
    while (fast) {
        slow = slow->next;  // 慢指针每次走一步
        ptr = fast->next;   // 临时保存快指针的下一个节点
        if (ptr == NULL) {   // 如果快指针走到末尾，则没有环，返回NULL
            return NULL;
        }
        fast = ptr->next;   // 快指针每次走两步

        // 如果快慢指针相遇，说明链表有环
        if (slow == fast) {
            // 如果有环，从链表头开始与慢指针一起移动，找到环的入口