写在前面
本篇为本人学习链表的过程中遇到的典型OJ题,于是整理出来分享思路和便于后续重新学习,每个标题均可跳转至对应习题,大多为Leetcode
链表OJ调试技巧
Leetcode中只能看到函数体,不能看到链表的具体情况,因此调试存在困难,自己搭建链表又过于繁琐,这里介绍一种很方便的链表调试技巧
原理如下
#include <stdio.h> #include <stdlib.h> #include <assert.h> struct ListNode { int val; struct ListNode* next; }; int main() { struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n1); struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n2); struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n3); struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n4); struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n5); n1->val = 1; n2->val = 2; n3->val = 3; n4->val = 4; n5->val = 5; n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n5; n5->next = NULL; }
我们只需要创建出每一个节点,接着把这些节点都连在一起,手动创建一个链表,链表中需要多少个元素自己搭建,这样可以便于调试,解决OJ中遇到的问题~~
介绍完调试的方法,正式总结链表中的OJ题目
移除链表元素
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点
1.遍历,是val的删掉
一种暴力解决的方法,图示如下
代码实现如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev=NULL; struct ListNode* cur=head; while(cur) { if(cur->val==val) { if(prev) { prev->next=cur->next; free(cur); cur=prev->next; } else { cur=head->next; free(head); head=cur; } } else { prev=cur; cur=cur->next; } } return head; }
2.遍历链表,把不是val的拿下来尾插
图解过程如下:
代码如下所示
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur=head; struct ListNode* newnode = NULL; struct ListNode* tail = NULL; while(cur) { if(cur->val!=val) { if(tail==NULL) { newnode=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 newnode; }
反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
下面介绍两种思路,均能解决问题
1.改变节点指向
定义三个节点(思考为什么定义三个而不是两个?)而后通过指针遍历把cur指向的节点方向指向前一个,然后通过迭代到末尾,当cur为空退出循环
代码实现如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { if(head==NULL) return NULL; struct ListNode* prev=NULL; struct ListNode* cur=head; struct ListNode* next=head->next; while(cur) { cur->next=prev; prev=cur; cur=next; if(next) next=next->next; } return prev; }
2.将每一个节点都头插
是一个新方法,只需要把新创建一个头,然后把每一个节点都头插进来即可,下面为原理图
代码实现如下
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* rhead = NULL; while (cur) { struct ListNode* next = cur->next; //头插 cur->next = rhead; rhead = cur; //迭代 cur = next; } return rhead; }
关于代码简洁性:
代码简洁程度取决于特殊情况的处理,例如,假设这里把next定义在while循环外,那么假设参数为NULL,就需要对特殊情况做处理,此时代码就多了if条件,整体来说简洁程度就降低了
简洁程度需要对特殊情况的处理足够好,才能足够精炼解决问题
链表的中间节点
给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
1.遍历链表求长度
代码实现如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { struct ListNode* plist=head; int flag=0; while(plist) { while(plist->next!=NULL) { plist=plist->next; flag++; } break; } flag+=1; flag=flag/2+1; for(int i=1;i<flag;i++) { head=head->next; } return head; }
2.快慢指针法
定义两个指针,一个指针是慢指针,每次走一步;一个指针是快指针,每次走两步。当快指针走到末尾时,慢指针走的位置恰好为整个链表的一半
相比起思路1来说,时间复杂度只是O(N),从时间复杂度来讲,这个方法更优
具体实现原理如下图所示
代码实现如下
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast!=NULL && fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } return slow; }
链表中倒数第K个节点
描述
输入一个链表,输出该链表中倒数第k个结点。
输入:1,{1,2,3,4,5}
输出:{5}
1.遍历求长度,根据k求结果
代码思路和上题十分类似,十分简单
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param pListHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* cur=pListHead; struct ListNode* prev=pListHead; int flag=0; while(cur) { cur=cur->next; flag++; } if(k>flag) { return NULL; } for(int i=0;i<flag-k;i++) { prev=prev->next; } return prev; }
2.仿照上题,快慢指针的方法解决
和上题相比,略有不同的一点是,上面的快指针每次走的是一样的,而对于这个题来说,假设K=4,那么就令快指针每次走四格,其余思路和上题类似
总结原理:这里既然要求的是倒数第k个,那么就令fast指针和slow指针之间差k个,然后两个一起走,当fast指针到末尾的时候,slow所在的位置就是fast位置减去它们一开始的距离差,也就是倒数k个的位置
整体思路是十分巧妙的,其实原理和方法1类似,都是找到最后一个元素,然后再找前面倒数的元素,但相比起来使用快慢指针的方法可以让时间复杂度缩短到最少
代码实现如下
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast=pListHead; struct ListNode* slow=pListHead; for(int i=0;i<k;i++) { if(fast) fast=fast->next; else return NULL; } while(fast) { fast=fast->next; slow=slow->next; } return slow; }
这里思考
第一次走k步和走k-1步有什么区别?
链表分割问题
题目描述
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针
由于题目描述中提到,不能改变原来的数据顺序,那么也就意味着只能尾插,因为尾插不会破坏数据顺序
于是,我们要做的实际上就是把小于val的单独拿出来,大于等于val的单独拿出来,创建两个节点让拿出来的这两份数据分别进行尾插,最后再实现链表的合并,即可解决这个问题
代码的实现也相对简单,代码实现如下
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* lesshead,*lesstail,*greaterhead,*greatertail; lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode)); greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode)); 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; pHead=lesshead->next; free(lesshead); free(greaterhead); return pHead; } };
环形链表
环形链表是链表中的一类题,先看环形链表的基本题型
- 如何判断一个链表是否带环?
- 可以使用快慢指针解法,快指针一次走两步,慢指针一次走一步,如果slow指针和fast指针在环中相遇,就说明链表带环,否则快指针独自走完就说明不带环
- 快指针一次走两步,慢指针一次走一步,这样的情况下快慢指针一定会相遇吗?
- 是的,一定会相遇,fast一次走两步,slow一次走一步,假设进环后它们之间相差的距离为N,那么它们两个每走一次,之间的距离就会少1,因此最后一定会相遇
- 快指针一次走三步,慢指针一次走一步,这样的情况下快慢指针一定会相遇吗?
- 不一定,这和它们之间的初始距离还有环的长度有关,假设进环的时候它们之间的距离为N,那么快慢指针每走一次,它们两个之间的距离就少2,如果这里的N为偶数,就会相遇,如果N为奇数,在此次追击中会错过,此时会进入下一次追击,假设环的长度为C,那么此时它们之间的距离为C-1,那么C-1如果为偶数快慢指针还能相遇,如果C-1为奇数快慢指针无法相遇
- 慢指针一次走一步,快指针一次走n步(n>2)可以吗?
- 假设快指针每次走三步,慢指针每次走一步,此时快指针先进环,慢指针后进环,假设慢指针进环的时候,快指针的位置如图所示,则此时按照上述方法进行绕环移动,每次快指针走三步,慢指针走一步,永远不会相遇,快指针刚好把慢指针套圈了,因此不可以
- 只有快指针走两步,慢指针走一步才可以,因为环的最小长度是1,即使套圈了两个指针也在相同的位置
- 给定一个带环的链表,如何求链表开始入环的第一个节点?
- 思路:一个指针从相遇点走,一个指针从起始点走,两个指针会在入口相遇
- 假设快指针一次走两步,慢指针一次走一步,那么快指针走的路程是慢指针走的路程的两倍,从起始点到进环口的距离设为L,进环口到相遇点之间的距离为X,环的长度为C,fast进入环后绕环n圈(假设初始为1)
- 慢指针走的路程为L+X,快指针走的路程为L+X+n* C,因此化简后L=n* C-X通常n为1,因此L=C-X,因此从上述结论成立