- 1. 移除链表元素
- 1.1 题目描述
- 1.2 解决思路
- 1.3 AC代码
- 2. 反转链表
- 2.1 题目描述
- 2.2 解决思路
- 2.3 AC代码
- 3. 链表的中间结点
- 3.1 题目描述
- 3.2 解决思路
- 3.3 AC代码
- 4. 链表中倒数第k个结点
- 4.1 题目描述
- 4.2 解决思路
- 4.3 AC代码
- 5. 合并两个有序链表
- 5.1 题目描述
- 5.2 解决思路
- 5.3 AC代码
- 6. 链表分割
- 6.1 题目描述
- 6.2 解决思路
- 6.3 AC代码
- 7. 链表的回文结构
- 7.1 题目描述
- 7.2 解决思路
- 7.3 AC代码
- 8. 相交链表
- 8.1 题目描述
- 8.2 解决思路
- 8.3 AC代码
- 9. 环形链表
- 9.1 题目描述
- 9.2 解决思路
- 9.3 AC代码
- 10. 环形链表 II
- 10.1 题目描述
- 10.2 解决思路
- 10.3 AC代码
- 11. 复制带随机指针的链表
- 11.1 题目描述
- 11.2 解决思路
- 11 .3 AC代码
前言：
- 在学习完链表部分（主要是单链表）相关函数，包括头插、头删、尾插、尾删等函数接口的实现思想，通过下面11道OJ题继续巩固知识。
- 数据结构主要学习其管理数据的方法思想，掌握他们处理数据的思想即可。
- 题目来源：LeetCode、牛客
- 实现：C语言
- 做题技巧：
- 画图，分析代码逻辑，走读代码分析
- 画图，手搓链表，VS调试
- . 题目链接如下：
- 移除链表元素
- 反转链表
- 链表的中间结点
- 链表中倒数第k个结点
- 合并两个有序链表
- 链表分割
- 链表的回文结构
- 相交链表
- 环形链表
- 环形链表 II
- 复制带随机指针的链表
1. 移除链表元素
LeetCode链接：移除链表元素
1.1 题目描述1.2 解决思路
要求：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
1.3 AC代码思路一：双指针
- 一般情况
- 使用双指针，一个cur，赋初值head，一个prev赋初值NULL，用cur遍历，直到cur==NULL结束
- 若cur->val != val，则先把cur的值赋给prev，再让cur往下走；若cur->val == val，则先操作prev->next = cur->next,完成链接后，free掉cur结点，在把prev->next赋值给cur（双指针迭代往后走）
- 重复2步骤，直到cur完成遍历
- 头删情况
- 最开始，如果cur->val == val，头删，更新head，先让head往后走，free掉cur，在让cur=head
- 继续判断
注意：这道题的头删没有使用二级指针，因为该函数带返回值。
思路二：遍历原链表，把不是val的结点拿出来进行尾插到新链表，再返回新链表的头
- 尾插效率较低，使用一个tail指针，赋初值NULL，标记尾巴，提高找尾效率
- 用cur指针遍历原链表，赋初值head
- 把不是val的结点依次尾插到tail->next,若是val的结点，则用一个指针del标记cur结点，先让cur往后走，再free是该结点
- 最后的tail->next赋值NULL（否则尾删情况会有野指针）
- 头删情况：最开始，把head赋值给cur之后，要置空，赋值NULL
思路三：在思路二的基础上改进，增加一个哨兵位的头结点，哨兵位是尾插时考虑**
思路一：
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 解决思路
要求：逆置单链表
2.3 AC代码思路一：使用头插思路，头插不需要考虑哨兵位，哨兵位是尾插时考虑
思路二：把指针的方向颠倒，空链表直接返回NULL
迭代过程：
- n2->next = n1（倒指向）
- n1 = n2
- n2 = n3
- n3 = n3->next（当n3 != NULL时才可操作）
- 结束条件：n2 == NULL
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 题目描述4.2 解决思路
要求： 找倒数第k个结点
4.3 AC代码使用快慢指针，让快指针先走K步，然后快慢指针同时走，快指针走到尾巴时，慢指针刚好是倒第k个结点
- 注意：当k大于链表长度，则不存在倒数第k个结点
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 解决思路
要求：合并两个升序链表成一个新的升序链表，返回新链表
5.3 AC代码利用归并排序思想，从头比较，取小的尾插到新链表
注意：
- 尾插效率低，要定义一个tail指针，标记链表尾巴
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 题目描述6.2 解决思路
要求：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前，返回重新排列后的链表的头指针。
6.3 AC代码定义两个新链表，都带哨兵位
注意：
- 分析极端场景：想极端场景
- 都比x小
- 都1比x大
- 有大有小
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 题目描述7.2 解决思路
要求：时间复杂度O(n)，空间复杂度O(1)
7.3 AC代码
- 注意：这种方法属于侵入式编程，破坏了源链表的结构，如果题目有要求，要恢复回去，当然这题没有要求，可不用管。
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 题目描述8.2 解决思路
要求：时间复杂度O(n)，空间复杂度O(1)
8.3 AC代码思路一：暴力对比，比较结点的地址，遍历A链表中的结点，与B链表中的每一个结点进行比较，这里比较的是地址
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
思路二：先判断相交，找尾结点，相交链表尾结点必定相等。相交的后半部是A和B相同的尾巴（后缀是相等的，相差在前面，先走差距步，相当于从同一起点走）
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 题目描述9.2 解决思路
要求：空间复杂度O(1),判断是否带环，返回bool值
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 解决思路
要求：判断相交，再找环入口点
10.3 AC代码思路一：数学问题
思路二：我们把meet断开，转换成相交链表求第一个交点的问题，但写起来比思路一复杂点，从这里也可看出，带环问题和相交问题可互相转换，这里就不给实现代码了。
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代码
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
- 如果有错误的地方请多多指教
