一、leetcode876. 链表的中间结点★
给定一个头结点为 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 之间。
链表不能通过下标来获得值，但是可以通过遍历，有三种方法
第一种：通过遍历链表，求得长度，可以取到中间值，二次遍历得到
第二种：单指针移动，类似第一种，求得长度，再移动到中间位置
第三种：快慢指针，fast移动2，slow移动1，当fast
指针到达末尾时，slow指针正好到中间
class Solution { public ListNode middleNode(ListNode head) { //数组遍历方法 // int left = 0; // ListNode linked[] = new ListNode[1100]; // while( head != null){ // linked[left++] = head; // head=head.next; // } // return linked[left/2]; // 单指针移动 // ListNode li = head; // int num = 0; // while(li != null){ // li = li.next; // ++num; // } // int k = 0; // li = head; // while(k< num/2) // { // li = li.next; // k++; // } // return li; //快慢指针移动 ListNode slow = head,fast=head; while( fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } }
二、leetcode19. 删除链表的倒数第 N 个结点★
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：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
这里用到了，删除节点的前驱和后继，所以创建一个哑针dummy作为head的前驱，剩下的代码都类似于第一个例题。
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0,head); ListNode cur = dummy; int length = qiulength(head); for(int i = 1;i<length-n+1;i++){ cur = cur.next; } cur.next = cur.next.next; ListNode a = dummy.next; return a; } public int qiulength(ListNode head){ int num = 0; ListNode cui = head; while(head!= null){ ++num; head=head.next; } return num; } }
