日本做暧视频观看网站/个人网站

---

前言：

1. 在学习完链表部分（主要是单链表）相关函数，包括头插、头删、尾插、尾删等函数接口的实现思想，通过下面11道OJ题继续巩固知识。
2. 数据结构主要学习其管理数据的方法思想，掌握他们处理数据的思想即可。
3. 题目来源：LeetCode、牛客
4. 实现：C语言
5. 做题技巧：

• 画图，分析代码逻辑，走读代码分析
• 画图，手搓链表，VS调试

---

• . 题目链接如下：

1. 移除链表元素
2. 反转链表
3. 链表的中间结点
4. 链表中倒数第k个结点
5. 合并两个有序链表
6. 链表分割
7. 链表的回文结构
8. 相交链表
9. 环形链表
10. 环形链表 II
11. 复制带随机指针的链表

---

1. 移除链表元素

LeetCode链接：移除链表元素

1.1 题目描述

要求：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

1.2 解决思路

思路一：双指针

• 一般情况

1. 使用双指针，一个cur，赋初值head，一个prev赋初值NULL，用cur遍历，直到cur==NULL结束
2. 若cur->val != val，则先把cur的值赋给prev，再让cur往下走；若cur->val == val，则先操作prev->next = cur->next,完成链接后，free掉cur结点，在把prev->next赋值给cur（双指针迭代往后走）
3. 重复2步骤，直到cur完成遍历

• 头删情况

1. 最开始，如果cur->val == val，头删，更新head，先让head往后走，free掉cur，在让cur=head
2. 继续判断

注意：这道题的头删没有使用二级指针，因为该函数带返回值。

---

思路二：遍历原链表，把不是val的结点拿出来进行尾插到新链表，再返回新链表的头

1. 尾插效率较低，使用一个tail指针，赋初值NULL，标记尾巴，提高找尾效率
2. 用cur指针遍历原链表，赋初值head
3. 把不是val的结点依次尾插到tail->next,若是val的结点，则用一个指针del标记cur结点，先让cur往后走，再free是该结点
4. 最后的tail->next赋值NULL（否则尾删情况会有野指针）
5. 头删情况：最开始，把head赋值给cur之后，要置空，赋值NULL

---

思路三：在思路二的基础上改进，增加一个哨兵位的头结点，哨兵位是尾插时考虑**

1.3 AC代码

思路一：

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* cur = head;struct ListNode* prev = NULL;while (cur){if (cur->val == val){//头删if (cur == head){head = cur->next;free(cur);cur = head;}else{//删除prev->next = cur->next;free(cur);cur = prev->next;}}else{prev = cur;cur = cur->next;}}return head;
}

思路二：

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* cur = head;struct ListNode* tail = NULL;head = NULL;while (cur){if (cur->val == val){struct ListNode* del = cur;cur = cur->next;free(del);}else{//尾插if (tail == NULL){head = tail = cur;}else{tail->next = cur;tail = tail->next;}cur = cur->next;}}if(tail)tail->next = NULL;return head;
}

思路三：

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur = head;struct ListNode* tail = NULL;//哨兵位节点head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));tail->next = NULL;while (cur){if (cur->val == val){struct ListNode* del = cur;cur = cur->next;free(del);}else{//尾插tail->next = cur;tail = tail->next;cur = cur->next;}}tail->next = NULL;struct ListNode* del = head;head = head->next;free(del);return head;
}

---

2. 反转链表

LeetCode链接：反转链表

2.1 题目描述

要求：逆置单链表

2.2 解决思路

思路一：使用头插思路，头插不需要考虑哨兵位，哨兵位是尾插时考虑

---

思路二：把指针的方向颠倒，空链表直接返回NULL

迭代过程：

1. n2->next = n1（倒指向）
2. n1 = n2
3. n2 = n3
4. n3 = n3->next（当n3 != NULL时才可操作）
5. 结束条件：n2 == NULL

2.3 AC代码

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

---

3. 链表的中间结点

LeetCode链接：链表的中间结点

3.1 题目描述

要求： 只能遍历链表一遍，返回链表中间节点

3.2 解决思路

使用快慢指针

3.3 AC代码

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

---

4. 链表中倒数第k个结点

牛客链接：链表中倒数第k个结点

4.1 题目描述

要求： 找倒数第k个结点

4.2 解决思路

使用快慢指针，让快指针先走K步，然后快慢指针同时走，快指针走到尾巴时，慢指针刚好是倒第k个结点

• 注意：当k大于链表长度，则不存在倒数第k个结点

4.3 AC代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow, * fast;slow = fast = pListHead;//fast先走k步while (k--){if (fast == NULL)//k比链表长度大，没有倒数第K个{return NULL;}fast = fast->next;}//再同时走while (fast){slow = slow->next;fast = fast->next;}return slow;
}

---

5. 合并两个有序链表

LeetCode链接：合并两个有序链表

5.1 题目描述

要求：合并两个升序链表成一个新的升序链表，返回新链表

5.2 解决思路

利用归并排序思想，从头比较，取小的尾插到新链表

注意：

1. 尾插效率低，要定义一个tail指针，标记链表尾巴

5.3 AC代码

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

6. 链表分割

牛客链接：链表分割

6.1 题目描述

要求：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前，返回重新排列后的链表的头指针。

6.2 解决思路

定义两个新链表，都带哨兵位

注意：

• 分析极端场景：想极端场景

1. 都比x小
2. 都1比x大
3. 有大有小
   

6.3 AC代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* greaterhead, *greatertail, *lesshead, *lesstail;greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));greatertail->next = NULL;lesstail->next = NULL;struct ListNode* cur = pHead;while(cur){if(cur->val < x){lesstail->next = cur;lesstail = lesstail->next;}else{greatertail->next =cur;greatertail = greatertail->next;}cur = cur->next;}lesstail->next = greaterhead->next;greatertail->next = NULL;struct ListNode* head = lesshead->next;free(greaterhead);free(lesshead);return head;}
};

---

7. 链表的回文结构

牛客链接：链表的回文结构

7.1 题目描述

要求：时间复杂度O(n)，空间复杂度O(1)

7.2 解决思路

• 注意：这种方法属于侵入式编程，破坏了源链表的结构，如果题目有要求，要恢复回去，当然这题没有要求，可不用管。

7.3 AC代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://调用以前写的链表找中间节点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;
}//调用以前写到逆置链表struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return NULL;struct ListNode* n1, * n2, * n3;n1 = NULL;n2 = head;n3 = n2->next;while (n2){//倒指向n2->next = n1;//迭代n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}return n1;
}//判断回文部分bool chkPalindrome(ListNode* A) {struct ListNode* head = A;struct ListNode* mid = middleNode(head);struct ListNode* rhead = reverseList(mid);while(head && rhead){if(head->val != rhead->val){return false;}else{head = head->next;rhead = rhead ->next;}}return true;}
};

---

8. 相交链表

LeetCode链接：相交链表

8.1 题目描述

要求：时间复杂度O(n)，空间复杂度O(1)

8.2 解决思路

思路一：暴力对比，比较结点的地址，遍历A链表中的结点，与B链表中的每一个结点进行比较，这里比较的是地址

1. 时间复杂度：O(n^2)
2. 空间复杂度：O(1)

---

思路二：先判断相交，找尾结点，相交链表尾结点必定相等。相交的后半部是A和B相同的尾巴（后缀是相等的，相差在前面，先走差距步，相当于从同一起点走）

8.3 AC代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA, *curB = headB;int lenA = 1, lenB = 1;while(curA->next){curA = curA->next;lenA++;}while(curB->next){curB = curB->next;lenB++;}if(curA != curB)//尾节点，无交点的情况{return NULL;}//走到这里，必定有交点//求第一个交点struct ListNode* shortlist = headA,* longlist = headB;if(lenA > lenB){shortlist = headB;longlist = headA;}int gap = abs(lenA - lenB);//求绝对值//长的先走gap步while(gap--){longlist = longlist->next;}//同时走while(shortlist != longlist){shortlist = shortlist->next;longlist = longlist->next;}return shortlist;
}

---

9. 环形链表

LeetCode链接：环形链表

9.1 题目描述

要求：空间复杂度O(1),判断是否带环，返回bool值

9.2 解决思路

带环链表的结构

注意：带环链表一遍历就会死循环

---

思路：使用快慢指针，转换成龟兔赛跑，追及问题。慢指针一次走一步，快指针一次走两步，如果带环，当快慢指针都进入环后，最终会相遇。

---

扩展：

1. 为什么慢指针一次走一步，快指针一次走两步，在带环链表中会出现相遇情况？

• 假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

2. 快指针一次走三步，四步……，还能不能相遇？

• 不一定能相遇

9.3 AC代码

bool hasCycle(struct ListNode *head) {struct ListNode* fast = head, *slow = head;while(fast && fast->next)//slow和fast都进入环后，追及问题{slow = slow->next;fast = fast->next->next;if(slow == fast)return true;}return false;
}

---

10. 环形链表 II

LeetCode链接：环形链表 II

10.1 题目描述

要求：判断相交，再找环入口点

10.2 解决思路

思路一：数学问题

---

思路二：我们把meet断开，转换成相交链表求第一个交点的问题，但写起来比思路一复杂点，从这里也可看出，带环问题和相交问题可互相转换，这里就不给实现代码了。

10.3 AC代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow,*fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){struct ListNode* meet = slow;while(meet != head){meet = meet->next;head = head->next;}return meet;}}return NULL;
}

---

11. 复制带随机指针的链表

LeetCode链接：复制带随机指针的链表

11.1 题目描述

要求：给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。要拷贝出一个同样的新链表。

11.2 解决思路

11 .3 AC代码

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {//1.struct Node* cur = head;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.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.尾插cur = head;struct Node* copyHead = NULL,*copyTail = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(copyTail == NULL){copyHead = copyTail = copy;}else{copyTail->next = copy;copyTail = copyTail->next;}cur->next = next;cur = next;}return copyHead;
}

---

学习记录：

• 本篇博客整理于2022.6.23~2022.7.3
• 如果有错误的地方请多多指教🌹🌹🌹