Leetcode -206.反转链表

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

示例 1：
输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]

示例 2：
输入：head = [1, 2]
输出：[2, 1]

示例 3：
输入：head = []
输出：[]

1. 从尾部开始向头部反转

这个思路的图如下：

代码：

		struct ListNode* reverseList(struct ListNode* head){//空链表返回空if (head == NULL){return NULL;}//定义两个结构体指针newhead，curstruct ListNode* newhead = head, * cur;//new找到链表的最后一个结点，最后返回这个结点while (newhead->next){newhead = newhead->next;}//将尾部赋给curcur = newhead;//head是原链表的头结点，所以反转之后head的next应该是NULL，若head的next不为空循环继续while (head->next){//每次进来都定义一个结构体指针newtail，从头开始找//直到newtail的next为cur停下struct ListNode* newtail = head;while (newtail->next != cur){newtail = newtail->next;}//将cur的next链接上一个结点cur->next = newtail;//如果cur的前一个结点是head，将head的next指向空，即为尾部if (cur->next == head){head->next = NULL;}//每次循环后更新curcur = newtail;}return newhead;}

2. 从头部开始反转

这个思路的图如下，prev记录上一个结点，最后也是返回prev，next是为记录下一个结点；

		struct ListNode* reverseList(struct ListNode* head){struct ListNode* prev = NULL, * curr = head;//当curr不为空循环继续while (curr){//next记录下一个结点//prev记录上一个结点struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}

Leetcode-876.链表的中间结点

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

示例 1：
输入：head = [1, 2, 3, 4, 5]
输出：[3, 4, 5]
解释：链表只有一个中间结点，值为 3 。

示例 2：
输入：head = [1, 2, 3, 4, 5, 6]
输出：[4, 5, 6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

1. 暴力循环法

这个思路就是统计链表的长度，然后将长度除以2取商，再从头开始走取商的步数即可；

		struct ListNode* middleNode(struct ListNode* head){//count记录链表的长度//curr用来返回int count = 0;struct ListNode* curr = head;//找空指针，统计链表长度while (curr){curr = curr->next;count++;}//让curr返回头部curr = head;//中间结点需要走的步长//用循环将curr往后走就行了int mid = count / 2;while (mid){curr = curr->next;mid--;}return curr;}

2. 快慢指针

这个思路的图如下：

初始化好的情况：（长度为奇数）

最后的结果：

长度为偶数：

结果图：

代码和注释：

		struct ListNode* middleNode(struct ListNode* head){//两个指针都从头开始struct ListNode* slow = head, * fast = head;//长度为偶数时fast为空，为奇数时fast->next为空while (fast && fast->next){//slow每次走一步//fast每次走两步slow = slow->next;fast = fast->next->next;}//最后slow就是要返回的指针return slow;}