- 题目1.移除链表元素
- 题目2.反转链表
- 题目3.链表的中间结点
- 题目4.链表中倒数第k个结点
- 题目5.合并两个有序链表
- 题目6.链表分割
题目1.移除链表元素前言: 这篇博客总结了几个比较常见的有关单链表的面试题,个人觉得题目比较好也比较经典,特地拿出来与小伙伴们分享。
题目链接
废话不多说直接上思路:
思路:
- 首先我们定义一个newhead指针来存放原来链表的head,并且通过newhead=newhead->next来向后遍历并且对比newhead->val是否和val相等来实现移除链表元素的目的
- 然而这时发现newhead是向前遍历了,也找到要删除的那个结点了,怎么实现删除呢? 由于单链表特殊的性质,每个结点只存放下一个结点的地址,我们删除结点的时候还需要知道前一个结点的地址,那么就需要再定义一个before指针来存放当前结点的上一个结点的地址。
- 然后,开始向前遍历,我们要考虑一些极端情况,例如头删(删除头部结点)的情况和非头删(删除非头部结点)的情况,这两个情况对于处理结点的方法是不同的,首先头删就是要改变头指针的指向,让头指针指向下一个结点,改变的是一个(结构体)指针变量的值,而非头删改变的是前一个结点(结构体)内部的next的指向,所以说两者的处理方法是不同的。
实现代码:
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*before=NULL; struct ListNode*newhead=head; while(newhead) { if(newhead->val==val) { if(newhead==head)//头删 { struct ListNode*tmp=head; head=head->next; free(tmp); newhead=head; } else//非头删 { struct ListNode*tmp=newhead; newhead=newhead->next; free(tmp); before->next=newhead; newhead=before->next; } } else//注意不要忘了向后迭代 { before=newhead;//注意不要忘了向后迭代 newhead=newhead->next; } } return head; }题目2.反转链表
题目链接
思路:
我们这里定义三个结构体指针n1、n2、n3,让n2指向头结点,n3指针指向n2的next,同时移动n1、n2、n3,三个指针同时每移动一次,就让n2的next指向一次n1,如此往复,当n2为NULL时,停止,然后返回n1指针即可。
实现代码:
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*n1=NULL;//三指针方法 struct ListNode*n2=head; struct ListNode*n3=NULL; while(n2) { n3=n2->next;//注意先后顺序,先有的n2,然后才有n3 n2->next=n1; n1=n2; n2=n3; } return n1; }题目3.链表的中间结点
题目链接
思路:
快慢指针,定义一个快指针和一个慢指针同时指向head,快指针一次走两步,慢指针一次走一步。 然后分情况:
当有奇数个结点时,fast为最后一个结点即fast->next为NULL时slow正好为中间结点;
当有偶数个结点时,fast为NULL时,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; }题目4.链表中倒数第k个结点
题目链接
思路:
普通解法:从头到尾遍历一遍,确定链表的个数n,然后从前往后再遍历n-k个结点就是链表中倒数第k个结点。但时间复杂度是O(2*n),n为链表的总长度,如果k总是在倒数第一个节点,那么此方法需要遍历链表2次。
快慢指针解法:总的来说就是先让fast先走k步,然后再同时走,fast和slow的距离差值不变,fast走到NULL的时候,slow所指向的那个结点就是倒数第k个结点。
但这道题目中有很多坑,我们需要注意各种极端情况 例如:k为小于等于0的时候,plistHead指向为空的时候,k大于结点个数的时候.
实现代码:
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* fast = pListHead; struct ListNode* slow = pListHead; if (pListHead != NULL || k > 0) {//k为小于等于0的时候,plistHead指向为空的时候的限制条件 while (k) {//先让fast走k步 if (fast == NULL) {//k大于结点个数的时候的限制条件 return NULL; } fast = fast->next; k--; } while (fast) { fast = fast->next; slow = slow->next; } return slow; } else { return NULL; } }题目5.合并两个有序链表
题目链接
思路:
这道题的创新点就是我们可以建立一个头结点(保镖结点guard),让头指针指向这个guard结点,然后在头插的时候,就可以直接往这个guard结点的next指针域链接即可,然后在创建一个newhead指针来记录guard的位置。最后我们直接返回newhead位置处的下一个结点的地址即可。试想如果没有头结点guard,我们不知道list1和list2哪个结点先要链接到guard的后面,那么针对list1和list2就要写两套头插和非头插的代码,先创建一个guard结点就可以省去这样的问题。
实现代码:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode*guard=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode*newhead=guard; while(list1&&list2) { if(list1->val题目6.链表分割val) { guard->next=list1; list1=list1->next; } else { guard->next=list2; list2=list2->next; } guard=guard->next; } if(list1==NULL) { guard->next=list2; } if(list2==NULL) { guard->next=list1; } struct ListNode*tmp=newhead; newhead=newhead->next; free(tmp); return newhead; }
题目链接
思路:
pHead结点从前向后遍历,然后创建两个保镖结点,一个结点链接比x小的结点,另一个结点链接比x大的结点,然后将两个链表合并。
这道题最重要的还是要建立两个保镖结点(guard),通过保镖结点来省去头插和非头插情况的代码,然后要注意画图去实现最终的代码,利用画图的方式就可以减少很多不必要的错误。
实现代码:
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here //两个链表一个放大的数据,一个放小的数据,最后将两个链表合并 struct ListNode* lessguard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* greaterguard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* lesshead = lessguard; struct ListNode* greaterhead = greaterguard; while (pHead) { if (pHead->val < x) { lessguard->next = pHead; lessguard = lessguard->next; } else { greaterguard->next = pHead; greaterguard = greaterguard->next; } pHead = pHead->next; } lessguard->next = greaterhead->next; free(greaterhead); greaterguard->next=NULL; struct ListNode*tmp=lesshead; lesshead=lesshead->next; free(tmp); return lesshead; } };
(C语言)链表经典oj题(二)
总结:
1、链表题要多多画图,代码要跟着图走。
2、注意指针下一步要走向哪里?是不动?还是要跳到下一个结点上?每次循环过后要注意更新结点。
3、多做题积累经验和方法,有些题目不是不会,只是从来都不知道有这样的方法。