力扣（LeetCode）数据结构练习题（2）

今天又写了两道关于链表的练习题，来给大家分享一下。巩固一下上一篇学到的链表知识，题目可以然我们更清楚的认识链表。

目录

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

现在我们来审题，题目很明了让我们反转一个单向链表，那么这里我们就可以简单思考一下思路了，有了思路我们就可以开始尝试一下写代码了。下面是我的方法：

方法一：

我们这里是将节点里的指针进行反转即可完成链表的反转。

/** * 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* n1=NULL; struct ListNode* n2=head; struct ListNode* n3=n2->next; while(n2) { n3=n2->next; n2->next=n1; n1=n2; n2=n3; } return n1; }

需要注意的是我们要考虑一下当head为空的情况下我们就直接返回NULL，就可以了。当不为空我们就可以直接取三个辅助变量进行 反转，我们只要将后一个的指针指向前一个即代码中

n2->next=n1;  然后我们就可以将代码往后遍历，这时n3的作用就是提前记住原来n2的next，然后令n2=n3，n1=n2，即可完成往后遍历。这是第一种方法，下面是第二种方法。

第二种方法：

我们可以通过创建一个新的反向链表即可。通过不断将原链表的字节一个一个头插也可以完成链表的反转。 

/** * 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* n=head; struct ListNode* newhead=NULL; struct ListNode* next=NULL; do { next=n->next; n->next=newhead; newhead=n; n=next; }while(n); return newhead; }

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

这里的题目也是很明了的，让我们返回一个中间节点就行了 ，那么我们要解决的就是如何找到中间节点，很多人想的办法是遍历一遍求出长度，然后又遍历到中间节点返回，但是这样就会增加时间复杂度了。所以我们可以用快慢指针来实现。块指针一次遍历两个节点，慢指针一次遍历一个节点。

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

如上fast为块指针，slow为慢指针。注意的是当fast和fast->next为空时都要结束循环，不能只是写fast为空时才结束循环，否则代码会出错。

好了今天文章就到这里结束了。