Leetcode -206.反转链表
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]
示例 2：
输入：head = [1, 2]
输出：[2, 1]
示例 3：
输入：head = []
输出：[]
- 从尾部开始向头部反转
这个思路的图如下：
代码：
struct ListNode* reverseList(struct ListNode* head) { //空链表返回空 if (head == NULL) { return NULL; } //定义两个结构体指针newhead，cur struct ListNode* newhead = head, * cur; //new找到链表的最后一个结点，最后返回这个结点 while (newhead->next) { newhead = newhead->next; } //将尾部赋给cur cur = 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; } //每次循环后更新cur cur = newtail; } return newhead; }
- 从头部开始反转
这个思路的图如下，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 ，返回第二个结点。
- 暴力循环法
这个思路就是统计链表的长度，然后将长度除以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; }
- 快慢指针
这个思路的图如下：
初始化好的情况：（长度为奇数）
最后的结果：
长度为偶数：
结果图：
代码和注释：
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; }
