链表OJ题型讲解与总结

目录

一.引言

二.链表题型详细讲解

一.移除链表元素

二.反转单链表

三.链表的中间结点

四.链表返回倒数第k个节点

五.合并两个有序链表

六.链表分割

七.链表的回文结构

八.相交链表

九.判断链表中是否有环

三.总结与提升

---

一.引言

   在我们学习完单链表与双链表后，真诚建议初学者能够掌握单双链表中：链表的初始化，尾插，头插，尾删，头删，固定位置插入以及删除等对应函数的编写，如果对这些内容仍然感到陌生，可以阅读本人上两篇博客对两种链表实现的详细讲解，如果已经掌握，可以来看看有关面试过程中可能会遇到的链表的OJ题型，经过整理如下：

二.链表题型详细讲解

一.移除链表元素

讲解：

        本题要求删除原链表中数据为val的节点，我们如何进行处理？如果直接用cur指针从原链表头节点进行判断，如果cur中val等于题目中给出的val那么将下一个节点连接到cur的next后面，这样的思路是否可以呢？其实是可以的，但是实现起来会很困难，试想：如果是1->2->6->6->6->3中要删除数据6呢？那么找到不是6的节点进行连接会变得很复杂。因此，这里我们采用另一种思路：我们创建一个新的头节点newhead，和尾节点tail，用cur在原链表中去遍历，如果cur中的val不是要删除的数据，我们就进行尾插，这样每次判断一个cur就让cur指向next，时间复杂度会更小，最后在tail不为NULL的条件下将tail->next赋值NULL，返回newhead，尝试实现如下：

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur=head;struct ListNode* tail=NULL;struct ListNode* newhead=NULL;if(head==NULL){return newhead;}else{while(cur){if(cur->val!=val){if(tail==NULL){newhead=cur;tail=cur;}else{tail->next=cur;tail=cur;}}cur=cur->next;}if(tail){tail->next=NULL;}return newhead;}
}

二.反转单链表

讲解：

        本题提供两种解法：让我们先来看第一种常规解法：先来定义一个newhead，这是我们最后要返回的头指针，随后是在原链表中负责遍历的cur指针，以及两个tmp和tmp地址备份指针tmp1，如果原链表为空，我们直接返回NULL，否则我们用tmp备份cur，tmp设为newhead，这里我使用了num来判断第一个尾插，如果num不为1那么就将新节点接在tmp后即可，直到cur走到了原链表的末尾，就返回newhead，代码：

//链表反转
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead = NULL, * cur = head, * tmp = NULL, * tmp1 = NULL;int num = 0;if (head == NULL){return NULL;}else{while (cur){tmp = cur;newhead = tmp;cur = cur->next;num++;if (num == 1){tmp->next = NULL;tmp1 = tmp;}else{tmp->next = tmp1;tmp1 = tmp;}}return newhead;}
}

        第二种解法要方便很多：我们使用三个指针来反转链表，如图：我们让n1为空，n2指针指向头节点，n3指针指向第二个节点，如果n2为空，就说明链表为空，那么直接返回NULL，如果不为空，我们让n2的next指向n1，然后让n1向前走，n2向前走，n3如果不为空就往下走：

n1,n2,n3往后走：

直到n2指向了末尾的NULL，这时n1就是反转链表的头指针，我们返回n1：

代码如下：

//三个指针来反转链表
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1 = NULL, * n2 = NULL, * n3 = NULL;n1 = NULL;n2 = head;if (head == NULL){return NULL;}n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}

三.链表的中间结点

讲解：

        两种解法：第一种是常规思路，我们可以用cur去遍历整个链表，来计算链表的长度，如果长度为奇数，我们返回cur从头节点经过(长度)/2个节点后指向的节点地址，如果长度为偶数，我们就返回cur从头节点经过(长度+1)/2个节点后指向的节点地址，代码如下：

struct ListNode* middleNode(struct ListNode* head) {struct ListNode* cur=head;int count=0;if(head==NULL){return NULL;}while(cur){cur=cur->next;count++;}cur=head;if(count%2==0){int num=(count+1)/2;while(num){cur=cur->next;num--;}return cur;}else{int num=count/2;while(num){cur=cur->next;num--;}return cur;}
}

        第二种解法使用快慢指针，快指针一次向前走两个，慢指针一次往前面走一个，这样当快指针为空或是快指针的next为空时，返回慢指针，就是题目要求返回的地址，图解如下：

同理，如果链表长度为偶数也同样适用：

代码如下：

struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast=head;struct ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}

四.链表返回倒数第k个节点

讲解：

        这里也有两个方法：第一种就是用cur指针从头指针开始去计算链表的结点个数，然后再让cur从头指针向下走长度-k个节点，返回最终的地址，这里直接介绍第二种简便方法：

        我们使用快慢指针，让快指针先走k个节点，然后让慢指针和快指针同时向前走，每次走一个节点，直到fast为NULL，这时返回slow指针的地址即可，图解：

代码如下：

int kthToLast(struct ListNode* head, int k) 
{struct ListNode* fast=head;struct ListNode* slow=head;while(k){fast=fast->next;k--;}while(fast){slow=slow->next;fast=fast->next;}return slow->val;
}

五.合并两个有序链表

讲解：

        这里可以定义两个指针，一个是最后要返回的newhead，一个是进行尾插时要用到的cur指针，然后再用cur1和cur2分别从list1和list2往下走，首先我们来判断list1和list2是否全部为空，或者其中有一个为空，前者直接返回NULL，后者返回另一个不为空的链表头指针即可，再就是对newhead的赋值，首先对两个链表的第一个节点数据进行比较，将较小的地址赋值newhead，在cur1和cur2都不指为空的时候对两个链表节点中的数据进行比较，每次将较小的节点进行尾插，如果相同，那么就进行两次尾插，直到cur1或是cur2中有一个指向空，直接将另一个不为空的链表接在cur后即可：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* cur1=list1;struct ListNode* cur2=list2;struct ListNode* newhead=NULL;struct ListNode* cur=NULL;if(list1==NULL&&list2==NULL){return newhead;}if(list1==NULL){return list2;}else if(list2==NULL){return list1;}else{if(cur1->val<cur2->val){newhead=cur1;cur1=cur1->next;}else{newhead=cur2;cur2=cur2->next;}cur=newhead;while(cur1&&cur2){if(cur1->val<cur2->val){cur->next=cur1;cur=cur->next;cur1=cur1->next;}else if(cur1->val>cur2->val){cur->next=cur2;cur=cur->next;cur2=cur2->next;}else{cur->next=cur2;cur=cur->next;cur2=cur2->next;cur->next=cur1;cur=cur->next;cur1=cur1->next;}}if(cur1==NULL){cur->next=cur2;   }else{cur->next=cur1;}return newhead;}
}

六.链表分割

举例：如果要将小于3的节点排在其他节点之前：

排序后：

讲解：

        解决本题最好的方法是使用哨兵位点，这样可以省去讨论链表头为空的情况，也可以防止很多对空指针进行解引用所引发的段错误，具体如何使用，请看图解：

我们使用malloc开辟两个头结点，用cur去遍历原链表，如果节点的val小于x，那么就把这个节点接到第一个头结点的尾上，如果大于等于x，就接到第二个头结点尾上，同时定义tail1和tail2两个指针来更好的进行尾插，当cur指向空时，代表遍历完成，这时把第二个头结点的next接到第一个tail1后面：

这样就构成了新链表，记住一定要在tail2后接上NULL，否则tail2->next会一直指向原链表的某个节点，有极大概率会构成死循环，最后我们返回第一个头结点的next，释放掉两个头结点：

 ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* gguard,*gtail,*lguard,*ltail,*cur=pHead;gguard=(struct ListNode*)malloc(sizeof(struct ListNode));gtail=gguard;lguard=(struct ListNode*)malloc(sizeof(struct ListNode));ltail=lguard;gtail->next=NULL;ltail->next=NULL;while(cur){if(cur->val<x){gtail->next=cur;gtail=gtail->next;}else {ltail->next=cur;ltail=ltail->next;}cur=cur->next;}gtail->next=lguard->next;ltail->next=NULL;struct ListNode* head=gguard->next;free(gguard);free(lguard);return head;}

七.链表的回文结构

讲解：

        相信在数组中判断一个字符串或者一个数组是否构成回文一定没少遇到，但是链表这里要复杂很多，如果分别从头从尾一个一个比较直到left下标大于right下标，这样会很复杂，因为链表没有下标，所以不能直接访问，如果要从尾部一个一个访问，不仅需要找尾，还需要记录尾结点的前一个结点地址，因此，这里我们可以换种思路，我们可以用快慢指针，找到中间那个链表的节点地址，然后从那个节点开始，重新产生一个反转的新链表，将新链表每一个节点的数据与原链表每一个节点的数据比较，一旦在两个链表走到空之前发现数据不同，就返回false，不构成回文链表，否则就返回true，构成回文链表：（ps:这里反转链表函数以及使用快慢指针找到链表中间节点在前文已经提及到），代码实现：

struct ListNode* find(struct ListNode* phead)
{struct ListNode* p1=phead;struct ListNode* p2=phead;while(p2&&p2->next){p2=p2->next->next;p1=p1->next;}return p1;
}
struct ListNode* reverse(struct ListNode* phead)
{struct ListNode* n1=NULL;struct ListNode* n2=phead;struct ListNode* n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}bool chkPalindrome(ListNode* phead) {struct ListNode* head1=find(phead);struct ListNode* head2=reverse(head1);while(phead&&head2){if(phead->val!=head2->val){return false;}phead=phead->next;head2=head2->next;}return true;}

八.相交链表

讲解：

        我们可以先将两个链表的头指针进行一个拷贝，然后让拷贝的指针去遍历两个链表，分别计算两个链表的长度，再让长度较长的那个链表向前走长度差个节点，再让两个同时先后走，如果两个链表存在同一个地址节点，那么就返回这个地址，如果两个链表都指向NULL都没有找到相同节点，就返回NULL：

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {struct ListNode* tail1=headA;int num1=0;int num2=0;int sub=0;struct ListNode* tail2=headB;while(tail1){tail1=tail1->next;num1++;}while(tail2){tail2=tail2->next;num2++;}if(num1>num2){sub=num1-num2;while(sub){headA=headA->next;sub--;}}else{sub=num2-num1;while(sub){headB=headB->next;sub--;}}while(headA&&headB){if(headA==headB){return headA;}headA=headA->next;headB=headB->next;}return NULL;
}

九.判断链表中是否有环

讲解：      

这样，如果fast或者fast->next指向空，那么就代表不存在节点，返回false，如果存在，就返回true：

bool hasCycle(struct ListNode *head) {struct ListNode* slow=head;struct ListNode* fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){return true;}}return false;
}

三.总结与提升

        在我们做链表Oj的时候，个人觉得要注意以下几点：

        1.注意判断头指针为空的情况；

        2.注意防止对空指针进行解引用；

        3.在进行尾插时，注意对尾指针指向空的处理；

        4.在实际编程中，注意对哨兵位点的返回值是否正确，以及对申请空间的释放；

        5.多动手画图分析，不要盲目做题，将原理剖析可以个更加高效的解题。

——————————————————    本文结束    ——————————————————