刷题专练之链表（一）

---

前言

以下是链表经常考的面试题，我在这里进行归纳和讲解，采取的是循序渐进的方式y一一讲解
当然，需要有链表基础，没有的话先看我前面的链表讲解

---

一、 移除链表元素

1.题目介绍

题目在力扣得的203. 移除链表元素

2.思路

本题有两种思路

1.使用带有哨兵位的头结点
2.将头结点为空时和头删时两种情况分开写

3.代码

1.带哨兵位的头节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode*dummyHead=(struct ListNode*)malloc(sizeof(struct ListNode));dummyHead->next=head;struct ListNode*prev= dummyHead;struct ListNode*cur=head;while(cur){struct ListNode*temp=cur;if(cur->val==val){struct ListNode*next=cur->next;prev->next=next;}else{prev=cur;  }cur=cur->next;   }return dummyHead->next;
}

2.不带哨兵位头节点的

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* prev=head;if(prev==NULL){return head;}struct ListNode*cur=prev->next;while(cur){if(prev->val==val&&prev->next!=NULL)//需要头删的情况，且之后有元素时{prev=prev->next;head=prev;cur=prev->next;}else if(cur->val==val){prev->next=cur->next;cur=cur->next;}else if(cur->val!=val){prev=cur;cur=cur->next;}}if(prev->val==val&&prev->next==NULL)//只有头节点的，而且需要头删的{head=NULL;return head;}return head;}

二、反转链表

1.题目介绍

题目在206. 反转链表

2.思路

此题用三个指针，prev保存前面得节点的地址，cur保存当前的地址，同时cur也是需要改变next的节点，next保存cur下一个节点的地址

最后返回prev即可

3.代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode*prev,*cur,*next;prev=NULL;cur=head;while(cur){next=cur->next;cur->next=prev;prev=cur;cur=next;}return prev;
}

三、链表的中间结点

1.题目介绍

题目在力扣的876. 链表的中间结点

2.思路

如果你做过数组的双指针题，那么这题你就会很快的做出来，如果你不能很快的理解我的做法，你可以到前面的数组的刷题里面去看，双指针法你就会炉火纯青了，好了，就算你不了解双指针法，也很快的理解我的做法

我们可以用一慢指针和快指针，快指针的速度是慢指针的2倍，即慢指针每走一步，快指针就走两步，我们假设这个链表的长度为n，而快指针走完这个链表时，慢指针刚好就指向链表的中间的位置

3.代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/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;}

四、链表的中间结点

1.题目介绍

题目在牛客链表中倒数第k个结点

2.思路

如果你做过我前面的一个题目，那么这题就非常好理解了

我们可以搞两个指针，一个slow，一个fast，让fast先走k步，然后当fast走完时，slow就是倒数第k个节点

3.代码

/*** 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 herestruct ListNode* fast=pListHead;struct ListNode* slow=pListHead;while(k--){if(fast==NULL){return NULL;}fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;
}