LeetCode20天刷题计划之Day5

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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= 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;}
};