876. 链表的中间结点
给定一个头结点为head的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]输出：此列表中的结点 3 (序列化形式：[3,4,5])返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]输出：此列表中的结点 4 (序列化形式：[4,5,6])由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于1和100之间。
第一种方法：遍历链表中的元素并放入数组中去，然后输出这个数组的中间元素就行，这样的好处就是可以直接用数组的下标来寻找元素。
//数组遍历法class Solution {public:ListNode* middleNode(ListNode* head) {vector<ListNode*> A = {head};while(A.back()->next != NULL){A.push_back(A.back()->next);}return A[A.size()/2];}};
第二种方法：两次使用单指针，第一次用单指针找到整个链表的元素个数，第二次使用单指针找到其中的中间元素。
/*** Definition for singly-linked list.* struct ListNode {*int val;*ListNode *next;*ListNode() : val(0), next(nullptr) {}*ListNode(int x) : val(x), next(nullptr) {}*ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Solution {public:ListNode* middleNode(ListNode* head) {int count = 0;//计数ListNode* node1 = head;while(node1 != nullptr){count++;node1 = node1->next;}int k = 0;//遍历找中间下标ListNode* node2 = head;while(k < count / 2){k++;node2 = node2->next;}return node2;}};
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1输出：[]
示例 3：
输入：head = [1,2], n = 1输出：[1]
提示：
链表中结点的数目为sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
这题和上面思路类似，可以先通过一次单指针count遍历找到链表元素的数量，然后在通过遍历整个链表元素进行一次删除操作，需要注意的是，链表中的头节点一般是没有前驱 的，如果遇到删除头节点的i情况是会报错的，所以一般需要在头节点前加上一个哑节点dummy，即dummy->next=head,这样就可以把链表所有元素当成一种情况对待，最后删除哑节点就🆗。对于删除倒数第N个元素，即对于前(count-n+1)个元素就是直接赋值就行，对于后面的需要进行删除。
/*** Definition for singly-linked list.* struct ListNode {*int val;*ListNode *next;*ListNode() : val(0), next(nullptr) {}*ListNode(int x) : val(x), next(nullptr) {}*ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Solution {public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* node1 = head;int count = 0;while(node1 != nullptr){count++;node1 = node1->next;}ListNode* dummy = new ListNode(0, head);//哑节点作为头指针的前驱int k = 1;//链表下标ListNode* node2 = dummy;while(k < count - n + 1){k++;node2 = node2->next;}node2->next = node2->next->next;ListNode * res = dummy->next;delete dummy;//删除哑节点return res;}};
如果觉得《LeetCode20天刷题计划之Day5》对你有帮助，请点赞、收藏，并留下你的观点哦！
