移除链表元素
给你一个链表的头节点
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题目还有许多,这里的题目只是链表题目的代表而已,并不是说这就是所有链表的题目了,有时间的话,我们还是得多去一些刷题平台做题。