移除链表元素
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点
思路一：一种比较普遍的方式，边遍历边找不同。我们可以通过定义两个指针，一个指向头节点，一个置为NULL。当遇到值为相同的时候，直接跳过去。指向下一位。同时，我们要去注意头删的问题，因为题目中给出的函数具有头结点head。
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 = head->next; free(cur); cur = head; } else { prev->next = cur->next; free(cur); cur = prev->next; } } else { prev = cur; cur = cur->next; } } return head; }
思路二：给一个新的链表，不是val的结点尾插到新链表即可。最后结点置为NULL。同时，还是要注意头结点的问题
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*cur = head; struct ListNode*newhead= NULL,*tail =NULL; while(cur) { if(cur->val!=val) { if(tail==NULL) { newhead = tail = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; } else { struct ListNode*del = cur; cur = cur->next; free(del); } } if(tail) tail->next = NULL; return newhead; }
我们不难发现，如果没有头结点，我们都要去关注，所以我们可以给出带头结点的单链表来进行实现：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*cur = head; struct ListNode*guard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode*tail = guard; while(cur) { if(cur->val != val) { tail->next = cur; tail = tail->next; cur = cur->next; } else { struct ListNode*del = cur; cur = cur->next; free(del); } } if(tail) tail->next = NULL; head = guard->next; free(guard); return head; }
有头结点之后我们就不需要去考虑删除第一个元素的事了。
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：比较简单，创建一个带头结点的链表，去比较数据的大小尾插到新链表的后面即可。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode*guard = (struct ListNode*)malloc(sizeof(struct ListNode)); guard->next = NULL; struct ListNode*cur1 = list1; struct ListNode*cur2 = list2; struct ListNode*tail = guard; while(cur1&&cur2) { if(cur1->val<cur2->val) { tail->next = cur1; cur1 = cur1->next; } else { tail->next = cur2; cur2 = cur2->next; } tail = tail->next; } if(cur1) { tail->next = cur1; } if(cur2) { tail->next = cur2; } struct ListNode*head = guard->next; free(guard); return head; }
反转链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
思路一：取结点头插到新的结点
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*cur = head; struct ListNode*newhead = NULL; while(cur) { struct ListNode*next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; }
思路二：直接把指针的方向进行翻转即可，使得链表翻转
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*cur = head; struct ListNode*prev = NULL; while(cur) { struct ListNode*next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }
链表的中间结点
给定一个头结点为
head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
思路：可以遍历一遍求出长度在除以2。不过我们采用另一种做法只遍历链表一遍即可，采用快慢指针即可。慢指针一次走一步，快指针一次走两步，我们要区分是奇数个结点还是偶数个结点。
对于奇数个：fast到尾，而slow刚好到中间结点
对于偶数个：fast走到空，而slow刚好走到中间结点。
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*fast = head; struct ListNode*slow = head; while(fast&&fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
思路：还是采用快慢指针的做法。slow每次走一步，而fast我们先让它去走K步。然后再同时走。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode*slow = pListHead,*fast = pListHead; while(k--){ //k大于链表长度 if(fast == NULL) return NULL; fast = fast->next; } while(fast){ fast = fast->next; slow = slow->next; } return slow; }
fast如果是先走K-1步呢？既把K–改为–K呢？里面的一些条件我们就需要去进行修改了（我们着重去分析一些边界的问题）：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode*slow = pListHead,*fast = pListHead; while(fast&&--k){ fast = fast->next; } if(fast == NULL) return NULL; while(fast->next){ fast = fast->next; slow = slow->next; } return slow; }
链表分割
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
思路：我们给出两个带头结点的新链表，值小于X的放在第一条链表，值大于X的放在第二条链表，最后两个新链表连接起来即可。同时，我们需要注意到如果链表为空的时候，我们可以画个图：
public: ListNode* partition(ListNode* pHead, int x) { // write code here ListNode*lessguard = (ListNode*)malloc(sizeof(ListNode)); lessguard->next = NULL; ListNode*lesstail = lessguard; ListNode*greaterguard = (ListNode*)malloc(sizeof(ListNode)); greaterguard->next =NULL; ListNode*greatertail = greaterguard; 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 = greaterguard->next; greatertail->next = NULL; pHead = lessguard->next; free(lessguard); free(greaterguard); return pHead; } };
回文链表
给你一个单链表的头节点
head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。
思路：找到中间位置，进行后半段逆置，进行比对即可,到最后都为NULL。这其实就是找链表的中间结点以及反转链表的合集：
class Solution { public: //反转链表 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; } //中间结点 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; } bool isPalindrome(ListNode* head) { // write code here struct ListNode* mid = middleNode(head); struct ListNode* ret = reverseList(mid); //1 2 3 2 1 //先反转中间以后的 //1 2 1 2 3 while (head && ret) { if (head->val == ret->val) { head = head->next; ret = ret->next; } else { return false; } } return true; } };
另一种解法：创建一个链表使之存放原链表的反转结果，然后在与原链表进行一一对比即可判断是否回文：
class Solution { public: bool isPalindrome(ListNode* head) { // write code here struct ListNode*cur = head; struct ListNode*newhead = NULL; struct ListNode*next = NULL; while(cur) { newhead = (struct ListNode*)malloc(sizeof(struct ListNode)); newhead->val = cur->val; newhead->next = next; next = newhead; cur = cur->next; } while(head) { if(newhead->val!=head->val) { return false; } else { newhead =newhead->next; head = head->next; } } return true; } };
相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
思路：首先需要确定有没有相交，在于尾结点的地址是否相同
找交点——求出长度，既是LenA和LenB的长度。长链表先走差距步，后再同时走，第一个相等就是所求的交点,因为我们已经判断了是否相交。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode*curA = headA,*curB = headB; int LenA = 0; int LenB = 0; while(curA) { curA = curA->next; LenA++; } while(curB) { curB = curB->next; LenB++; } if(curA!=curB) { return NULL; } struct ListNode*longList = headA,*shortList = headB; if(LenA<LenB) { longList = headB; shortList = headA; } int gap = abs(LenA-LenB); while(gap--) { longList = longList->next; } while(longList != shortList) { longList = longList->next; shortList = shortList->next; } return longList; }
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
思路：带环链表不能遍历。。。我们可以用快慢指针来解决这道题目,快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾：
bool hasCycle(struct ListNode *head) { struct ListNode*slow = head; struct ListNode*fast = head; while(fast &&fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { return true; } } return false; }
延伸问题
为什么快指针每次走两步，慢指针走一步可以追上，会不会错过？
- slow一次走一步，fast一次走三步呢❓
- slow一次走一步，fast一次走X步呢❓
- slow一次走Y步，fast一次走X步呢❓
后面的问题也是类似的解法，对于slow一次走一步，fast一次走X步呢？每次的距离缩小X-1
而对于slow一次走Y步，fast一次走X步呢？每次的距离缩小X-Y
这其实就是相对距离缩小的问题
环形链表 II😱
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路一：这里先说一个结论(入环的第一个节点)：
让一个指针从链表起始位置开始遍历链表，同时让一个指针从相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode*slow = head,*fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { struct ListNode*meet = slow; while(head!=meet) { head = head->next; meet = meet->next; } return meet; } } return NULL; }
思路二：转化成相交链表，从相遇点断开后，作为一个链表，另一个链表从头开始，链表开始入环的第一个节点就相当于这两个链表的交点，而找链表的交点就是上面的题目相交链表。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode*curA = headA,*curB = headB; int LenA = 0,LenB = 0; while(curA) { curA = curA->next; LenA++; } while(curB) { curB = curB->next; LenB++; } if(curA != curB) { retur NULL; } struct ListNode*longlist = headA,*shortlist = headB; if(LenA<LenB) { longlist = headB; shortlist = headA; } int gap = abs(LenA-LenB); while(gap--) { longlist = longlist->next; } while(longlist!=shortlist) { longlist = longlist->next; shortlist = shortlist->next; } return longlist; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode*slow = head,*fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { //找到相遇的点 struct ListNode*meet = slow; struct ListNode*next = meet->next; //断开 meet->next = NULL; struct ListNode*enterNode = getIntersectionNode(head,next); //恢复原来的链表 meet->next = next; return enterNode; } } return NULL; }
复制带随机指针的链表😰
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
本题较难。如果我们每个节点都去进行复制，这道题的random我们较难去处理：
struct Node* copyRandomList(struct Node* head) { //copy节点 struct Node* cur = head; struct Node*copy = NULL; struct Node*next = NULL; while(cur) { //赋值链接 next = cur->next; copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; cur->next = copy; copy->next = next; //迭代 cur = next; } //更新copy的random cur = head; while(cur) { copy = cur->next; if(cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } //迭代 cur = cur->next->next; } //copy节点解下来链接在一起，恢复原链表 struct Node*copyHead = NULL,*copyTail = NULL; cur = head; while(cur) { copy = cur->next; next = copy->next; //取节点尾插 if(copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail->next = copy; copyTail = copyTail->next; } //恢复原链表 cur->next = next; cur = next; } return copyHead; }
总结
- 通过上面的链表OJ题目，我们对于链表有了更深的了解，同时学会了一些解题的方法，同时，对于做题，我们首先要做的是去理解题目的含义，然后要多去动手画图，方便我们更好地处理一些细节的东西。
- 当然，链表的OJ题目还有许多，这里的题目只是链表题目的代表而已，并不是说这就是所有链表的题目了，有时间的话，我们还是得多去一些刷题平台做题。
