数据结构与算法学习-链表下
2019-05-05 本文已影响6人
青争哥哥_
前言
上一篇文章讲了链表相关的概念，这篇主要记录的是和链表相关的算法以及一些写好链表算法代码相关的技巧。
实现单链表、循环链表、双向链表，支持增删操作
1. 单链表
// 头文件 ----------------------------------------------------------
typedef struct _node {
int value; // 数据域
struct _node *next; // 指针域
} Node;
typedef struct _list {
Node *head; // 头指针
Node *tail; // 尾指针
int length; // 链表的长度
} SingleList;
// 创建链表
SingleList * creatList(void);
// 释放链表
void freeList(SingleList *pList);
// 给链表末尾添加一个结点
void appendNode(SingleList *pList, int value);
// 删除末尾结点
void removeLastNode(SingleList *pList);
// 在指定位置插入一个结点
void insertNodeAtIndex(SingleList *pList, int index, int value);
// 在指定位置删除一个结点
void deleteNodeAtIndex(SingleList *pList, int index);
// 打印链表中所有结点值
void printList(SingleList *pList);
// .m 文件 --------------------------------------------------------------------
SingleList * creatList(void)
{
SingleList *pList = (SingleList *)malloc(sizeof(SingleList));
pList->head = NULL;
pList->tail = NULL;
pList->length = 0;
return pList;
}
// 释放链表
void freeList(SingleList *pList)
{
if(pList == NULL) {
return;
}
if (pList->head == NULL) {
free(pList);
return;
}
// 用q 来保存下一个p节点
Node *p, *q = NULL;
for (p = pList->head; p; p = q) {
q = p->next;
free(p);
}
free(pList);
}
// 给链表末尾添加一个结点
void appendNode(SingleList *pList, int value)
{
// 制造一个结点，加入链表中去
Node *p = (Node *)malloc(sizeof(Node));
p->value = value;
p->next = NULL;
// 如果链表为空
if (pList->head == NULL) {
// p 结点就是头结点，也是尾结点
pList->head = pList->tail = p;
} else {
pList->tail->next = p;
// 更新尾指针
pList->tail = p;
}
pList->length += 1;
}
// 删除末尾结点
void removeLastNode(SingleList *pList)
{
if (pList->tail == NULL) {
// 链表为空
printf("链表为空!!!!");
return;
}
if (pList->head == pList->tail) {
// 链表只有一个结点
pList->head = pList->tail = NULL;
pList->length -= 1;
return;
}
// 需要先遍历的到尾结点的上一个结点，然后删除尾结点，再更新尾结点
Node *p = pList->head;
while (p->next != pList->tail) {
p = p->next;
}
// 释放尾结点
free(pList->tail);
p->next = NULL;
pList->length -= 1;
// 更新尾结点
pList->tail = p;
}
// 在指定位置插入一个结点，下标从 0 开始
void insertNodeAtIndex(SingleList *pList, int index, int value)
{
if (index >= pList->length || index < 0) {
// 下标越界
printf("下标不合法!!!");
return;
}
// 制造一个结点，加入链表中去
Node *s = (Node *)malloc(sizeof(Node));
s->value = value;
s->next = NULL;
Node *p = pList->head;
Node *q = NULL;
for (int i = 0; i < pList->length; i ++) {
// 找到了要插入的节点位置
if (i == index) {
if (i == 0) {
// 插入到头结点
s->next = pList->head;
pList->head = s;
} else {
s->next = p;
q->next = s;
}
pList->length += 1;
break;
}
q = p;
p = p->next;
}
}
// 在指定位置删除一个结点
void deleteNodeAtIndex(SingleList *pList, int index)
{
if (index >= pList->length || index < 0) {
// 下标越界
printf("下标不合法!!!");
return;
}
Node *p = pList->head;
Node *q = NULL;
for (int i = 0; i < pList->length; i ++) {
if (index == i) {
if (i == 0) {
// 首节点，将链表的首节点指向
pList->head = p->next;
} else {
q->next = p->next;
}
free(p);
pList->length -= 1;
break;
}
// 用 q 来记录 p 的上一个结点
q = p;
p = p->next;
}
}
// 打印链表中所有结点值
void printList(SingleList *pList)
{
Node *p = pList->head;
if (p == NULL) {
printf("链表为空!!!");
}
while (p) {
printf("%d\n", p->value);
p = p->next;
}
}
// 测试代码 ------------------------------------------------------
SingleList *pList = creatList();
// 加入结点
printf("------加入结点\n");
appendNode(pList, 10);
appendNode(pList, 20);
appendNode(pList, 30);
appendNode(pList, 40);
appendNode(pList, 50);
printList(pList);
printf("------删除结点\n");
removeLastNode(pList);
printList(pList);
printf("------插入新结点到头结点位置\n");
insertNodeAtIndex(pList, 0, 100);
printList(pList);
printf("------插入新结点到尾结点位置\n");
insertNodeAtIndex(pList, 4, 200);
printList(pList);
printf("------插入新结点到中间结点位置\n");
insertNodeAtIndex(pList, 1, 300);
printList(pList);
printf("------插入新结点到中间结点位置\n");
insertNodeAtIndex(pList, 3, 500);
printList(pList);
printf("------删除头结点\n");
deleteNodeAtIndex(pList, 0);
printList(pList);
printf("------删除尾结点\n");
deleteNodeAtIndex(pList, 6);
printList(pList);
printf("------删除中间结点\n");
deleteNodeAtIndex(pList, 3);
printList(pList);
printf("------删除中间结点\n");
deleteNodeAtIndex(pList, 2);
printList(pList);
// 释放链表
freeList(pList);
// 打印日志 ---------------------------------------------------
------加入结点
10
20
30
40
50
------删除结点
10
20
30
40
------插入新结点到头结点位置
100
10
20
30
40
------插入新结点到尾结点位置
100
10
20
30
200
40
------插入新结点到中间结点位置
100
300
10
20
30
200
40
------插入新结点到中间结点位置
100
300
10
500
20
30
200
40
------删除头结点
300
10
500
20
30
200
40
------删除尾结点
300
10
500
20
30
200
------删除中间结点
300
10
500
30
200
------删除中间结点
300
10
30
200
Program ended with exit code: 0
2. 循环链表
循环链表就是尾结点的next指针指向的是头结点,这样链表就构成了环，实现起来和单链表差不多。主要是循环的条件变成了 p->next != head，这里用到了哨兵结点，关键代码如下：
// 创建链表，至少有一个结点
CycleList * creatList(void)
{
CycleList *pList = (CycleList *)malloc(sizeof(CycleList));
// 哨兵结点
Node *head = (Node *)malloc(sizeof(Node));
// 自己的 next 指针指向自己
head->next = head;
pList->head = head;
return pList;
}
// 在指定位置插入一个结点
void insertNodeAtIndex(CycleList *pList, int index, int value)
{
int length = listLength(pList);
if (index < 0 || index > length) {
printf("下标不合法!!!!");
return;
}
// 在末尾插入
if (index == length) {
appendNode(pList, value);
return;
}
// 在中间插入
Node *p = pList->head;
int i = 0;
while (p->next != pList->head) {
if (i == index) {
// 插入结点
Node *s = (Node *)malloc(sizeof(Node));
s->value = value;
s->next = p->next;
p->next = s;
}
p = p->next;
i++;
}
}
// 在指定位置删除一个结点
void deleteNodeAtIndex(CycleList *pList, int index)
{
int length = listLength(pList);
if (index < 0 || index >= length) {
printf("下标不合法!!!!");
return;
}
Node *p = pList->head;
int i = 0;
while (p->next != pList->head) {
if (i == index) {
if (index == length - 1) {
// 在末尾删除
Node *q = p->next;
p->next = pList->head;
free(q);
return;
} else {
// 在中间删除
Node *q = p->next;
p->next = p->next->next;
free(q);
}
}
p = p->next;
i++;
}
}
3. 双向链表
双向链表既有前驱指针，又有后继指针，所以可以双向遍历。关键代码如下：
// 指定位置插入结点
void insertNodeAtIndex(ListNode *head, int index, int value)
{
int length = listLength(head);
if (index < 0 || index > length) {
printf("下标不合法！！！\n");
return;
}
// 在末尾插入
if (index == length) {
appendNode(head, value);
return;
}
// 在中间插入
ListNode *p = head;
int i = 0;
while (p && p->next) {
if (index == i) {
// 插入结点
ListNode *s = (ListNode *)malloc(sizeof(ListNode));
s->value = value;
// 新结点的前驱结点为上一个结点
s->prev = p;
// 新结点的下一个结点的前驱结点为新结点
p->next->prev = s;
// 新结点的后继结点为p的下一个结点
s->next = p->next;
// p 结点的后继结点为s
p->next = s;
}
p = p->next;
i++;
}
}
// 指定位置删除结点
void deleteNodeAtIndex(ListNode *head, int index)
{
int length = listLength(head);
if (index < 0 || index >= length) {
printf("下标不合法！！！\n");
return;
}
ListNode *p = head;
ListNode *q = NULL;
int i = 0;
while (p && p->next) {
if (index == i) {
// 保存要删除的结点
q = p->next;
if (index == length - 1) {
// 删除最后一个结点
// 直接让p的next指针置空
p->next = NULL;
} else {
// 删除中间结点
// p 的下一个结点的下一个结点的前驱结点变成p
p->next->next->prev = p;
// p的下一个结点变成下下个结点
p->next = p->next->next;
}
// 释放要删除的结点
free(q);
}
p = p->next;
i++;
}
}
实现两个有序的链表合并为一个有序链表
解题思路：
这个题和合并两个有序的数组为一个有序数组的思路一样，申请第三个链表，长度链表同时遍历，谁的结点比较小就将谁的结点插入到新链表中，最后短链表遍历完，再将长链表中剩余的结点插入到新的链表中去，时间复杂度只有一层循环遍历是 O(n)，空间复杂度额外申请了一个 ListNode 空间，来存储新的链表结点，所以是 O(n)。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
// 异常判断
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
struct ListNode *firsthead = l1;
struct ListNode *secouondhead = l2;
// 用第三个链表来保存数据
struct ListNode *l3 = malloc(sizeof(struct ListNode));
// 临时变量，指向新申请的结点l3
struct ListNode *thirdhead = l3;
// 同时遍历两个长短链表
while (firsthead && secouondhead) {
// 那个链表的结点值比较小就将该结点插入到新链表中
if (firsthead->val <= secouondhead->val) {
l3->next = firsthead;
firsthead = firsthead->next;
}else {
l3->next = secouondhead;
secouondhead = secouondhead->next;
}
l3 = l3->next;
}
if (firsthead == NULL) {
// 还剩第二个链表，将第二个链表中的所有结点都插入到新链表中
while (secouondhead) {
l3->next = secouondhead;
secouondhead = secouondhead->next;
l3 = l3->next;
}
}
if (secouondhead == NULL) {
// 还剩第一个链表，将第一个链表中的所有结点都插入到新链表中
while (firsthead) {
l3->next = firsthead;
firsthead = firsthead->next;
l3 = l3->next;
}
}
// 该结点的next指针指向的才是真正合并后的第一个结点
return thirdhead->next;
}
实现求链表的中间结点
快慢指针就可以实现，快指针走两步，慢指针走一步，遍历完整个链表慢指针指向的就是中间节点。默认链表没有环。如果链表长度是偶数，中间节点取的是下中位节点。
// 求中间节点
Node *getMiddleNode(SingleList *pList)
{
if (pList->head == NULL) {
printf("链表为空！！！");
}
// 快指针，每次走两步
Node *fast = pList->head;
// 慢指针，每次走一步
Node *slow = pList->head;
while (slow && fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
// 测试代码 ---------------------------------
SingleList *pList = creatList();
// 加入结点
printf("------加入结点\n");
appendNode(pList, 10);
appendNode(pList, 20);
appendNode(pList, 30);
appendNode(pList, 40);
appendNode(pList, 50);
printList(pList);
// 中间节点
Node *mid = getMiddleNode(pList);
printf("mid.value = %d\n", mid->value);
// 打印日志 ---------------------------------
------加入结点
10
20
30
40
50
mid.value = 30
leetcode 上相关练习
1. 反转一个单链表
struct ListNode* reverseList(struct ListNode* head){
if(head == NULL || head->next == NULL) return head;
struct ListNode* provious = NULL;
struct ListNode* current = head;
while(current) {
// 保存当前结点的下一个结点指针
struct ListNode* temp = current->next;
// 将当前节点的next指针指向上一个结点
current->next = provious;
// 将当前节点赋值给上一个结点
provious = current;
// 指向下一个结点
current = temp;
}
// 最后一个provious就是链表的头指针
return provious;
}
2. 两两交换链表中的节点
解题思路：
每次走两步遍历链表，每次两两交换都需要修改三个结点指针的指向，需要三个变量来保存。其中 previous 用来保存上一次的 current 指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode *current = head;
struct ListNode *previous = NULL;
while (current && current->next) {
// 当前指针的下一个结点
struct ListNode *a = current->next;
// 当前指针的下下一个结点
struct ListNode *b = a->next;
// 交换
a->next = current;
current->next = b;
if (previous) {
// 将上次的指针指向交换后的结点
previous->next = a;
} else {
// 重新赋值给头指针
head = a;
}
// 保存上一次的指针
previous = current;
// 每次走两步
current = b;
}
return head;
}
3. 判断链表是否有环
解法一：
使用一个散列表老保存遍历过的结点，每次遍历链表都去散列表中查找，判断当前结点是否已经存在散列表中，如果在散列表中找到，那么就有环，如果直到链表遍历结束也没找到，就没有环。这种的时间复杂度是 O(n)，空间复杂度是 O(n)。
解法二：
使用快慢指针，遍历链表，快指针每次走两步，慢指针每次走一步，判断快慢指针是否相遇，如果相遇则链表有环，如果遍历完链表也没有相遇，说明没有环。这种解法的时间复杂度是 O(n)，空间复杂度是 O(1)。
// 解法二
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
if(head == NULL || head->next == NULL) return false;
// 快慢指针
struct ListNode *fast = head;
struct ListNode *slow = head;
while(slow && fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
// 如果快慢指针相遇，就表示有环
if(slow == fast) {
return true;
}
}
return false;
}
4. 环形链表
解题思路：
给定一个链表，返回链表开始入环的第一个节点。这里运用到了一个几何上的数学公式，快指针和慢指针走一移动直到第一次相遇在 X 结点，假设慢指针走了 N 步，快指针就走了 2N 步，假设入环的第一个节点为 Z，则会有起点到 Z 的距离会等于 X 结点到 Z 的距离，所以在快慢指针判断链表有环后只需要让快指针从头开始一步一步走，以此同时慢指针继续向前走，两者就会在第一个入环节点为 Z 相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
struct ListNode *fast = head;
struct ListNode *slow = head;
// 快慢指针检测是否有环
while(slow && fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow) {
break;
}
}
// 有环
if(fast == slow) {
// 寻找环的入环结点
fast = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return fast;
} else {
return NULL;
}
}
5. 每 k 个节点一组翻转链表
解题思路：
每 k 个结点一组翻转，可以使用递归实现，每一组翻转完成后，传入下一个结点的指针，递归调用，递归的基线条件是剩余的结点个数小于k，然后需要将每一组翻转翻转的组尾的 next 指针指向下一组的组头。
/*
* @lc app=leetcode.cn id=25 lang=c
*
* [25] k个一组翻转链表
*
* https://leetcode-cn.com/problems/reverse-nodes-in-k-group/description/
*
* algorithms
* Hard (48.65%)
* Total Accepted: 10.3K
* Total Submissions: 20.3K
* Testcase Example: '[1,2,3,4,5]\n2'
*
* 给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
*
* k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
*
* 示例 :
*
* 给定这个链表：1->2->3->4->5
*
* 当 k = 2 时，应当返回: 2->1->4->3->5
*
* 当 k = 3 时，应当返回: 3->2->1->4->5
*
* 说明 :
*
*
* 你的算法只能使用常数的额外空间。
* 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
*
*
*/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k){
// 异常判断
if (head == NULL || head->next == NULL || k < 2) {
return head;
}
// 判断链表中的结点是否大于等于k个，还够不够翻转
struct ListNode *temp = head;
for (int i = 0; i < k; i++, temp = temp->next) {
if (temp == NULL) {
// 不够翻转，基线条件
return head;
}
}
// k个结点一组进行结点的翻转
struct ListNode *current = head;
struct ListNode *previous = NULL;
for (int i = 0; i < k; i ++) {
struct ListNode *temp = current->next;
current->next = previous;
previous = current;
current = temp;
}
// 递归条件，正好每组的头结点翻转完成后到组尾，将next指针指向下一组的组头结点
head->next = reverseKGroup(current, k);
// 返回头结点指针
return previous;
}
总结一些技巧
1. 理解指针的概念
指针保存的是变量的内存地址，通过指针就能找到这个变量，如链表中经常写的 p->next = q，意思是说 p 结点的next 指针保存了 q 结点的内存地址。
2. 警惕指针丢失和内存泄漏
对于链表的插入操作，需要注意代码的先后顺序，写反了就会发生内存泄漏，删除操作需要手动 free 结点的内存。
// 在 a 结点和 b 结点中间插入 x 结点，p 指针指向 a 结点， 正确写法✔️
x->next = p->next->next;
p->next = x;
// 错误写法，这个时候 p->next 已经不指向 b 了，而是指向 x。❌
p->next = x;
x->next = p->next;
3. 善用哨兵结点简化问题
有时候处理头指针和尾指针是需要特别的处理，代码也不统一，引入哨兵结点后，可以简化问题，哨兵结点不存储数据，只是 next 指针指向链表的实际结点，这样，头结点的逻辑就可以和其他结点一样了，不用特别处理。这样就简化了代码逻辑。如链表的插入逻辑和删除逻辑，不用哨兵结点的话，就需要区别对待头结点和尾结点。引入哨兵结点的链表叫做带头链表，相反没有哨兵结点的链表叫做不带头链表。如图所示：
带头链表
4. 重点留意边界条件处理
写链表代码很容易出错，需要考虑的边界条件有很多，有些额外需要做特别处理，需要特别考虑如：
- 链表为空时，代码是否正常？
- 链表只有一个结点时，代码是否正常？
- 链表只包含两个结点时，代码是否正常？
- 处理头结点和尾结点，代码是否正常？
5. 画图辅助分析
如果空间想象能力不够好，特别是多层循环或者递归时，画图辅助分析可以帮助定位每一步的变量值，指针是怎么指向的，也可以在没有思路的时候通过画图辅助分析一步一步的总结归纳出规律来，这个时候算法思路就变清晰一些。我写快慢指针检测环，定位链表中点和两两翻转链表代码时就是在笔记上一步一步推到出代码规律来的。
6. 多写多练，掌握套路
很多链表相关的写法其实写多了会发现很多类似的思路，如快慢指针思路，既可以用来定位链表中间结点，又可以用来检测环，复杂点的问题也一般可以分割成小问题来处理。
扩展阅读
数据结构与算法学习-链表上
《算法图解》读书笔记—像小说一样有趣的算法入门书
数据结构与算法学习-数组
数据结构与算法学习-复杂度分析
数据结构与算法学习-开篇
分享个人技术学习记录和跑步马拉松训练比赛、读书笔记等内容，感兴趣的朋友可以关注我的公众号「青争哥哥」。
青争哥哥
