一、题目
1、审题
2、分析
去除链表的倒数第 n 个元素，并返回链表
二、解答
1、分析：
方法一：
a、遍历确定链表节点个数 total；
b、去除第 total - n 个节点；
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { int total = 0; ListNode tempNode = head; while(tempNode != null) { total++; tempNode = tempNode.next; } if(total < n) return head; else if(total == n) return head.next; int index = 1; tempNode = head; while(index++ < total - n) tempNode = tempNode.next; tempNode.next = tempNode.next.next; return head; }}
方法二：
a、采用指针，slow 指向头结点，fast 指向距离头结点为 n 的节点；
b、slow 与 fast 一起向后移动，当 fast指向节点的 next 为空时，去除 slow 的next 节点；
注意： 距离为 n 时，要删除的是 距离为 n - 1 的数， 即第 n 个数。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head.next == null) return null; int distant = 1; ListNode slow = head, fast = head; // distant = n - 1 while(distant++ < n) fast = fast.next; // keep the distant = n if(fast == null) return head.next; else if(fast.next != null) fast = fast.next; else // remove Node slow return slow.next; while(fast.next != null) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return head; }}
同方法二，更简洁的实现方法；
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode fast = head; ListNode slow = head; for (int i = 0; i < n; i++) { // distant is n fast = fast.next; } ListNode prev = null; while(fast != null) { // 当 slow 指向的为 倒数第 n 个元素，即所要删除的元素时跳出循环 prev = slow; slow = slow.next; fast = fast.next; } if(prev == null) // when slow = head , fast is NULL head = head.next; else prev.next = slow.next; // fast is return head; }