1、題干
給你一個鏈表，刪除鏈表的倒數第 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
2、解題
前提給定：（鏈表節點的定義和鏈表的形成）
鏈表節點定義如下：
// 鏈表節點
public class ListNode {int val;ListNode next;ListNode() {}ListNode(int x) {val = x;}
}
鏈表構建過程示例：（如上示例1）
public static void main(String[] args) {ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);ListNode node5 = new ListNode(5);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;ListNode node = removeNthFromEnd(node1, 2);while (node != null) {System.out.println(node.val);node = node.next;}}
方法一：（計算鏈表長度）
通過一個臨時節點，指向頭結點，依次遍歷到尾節點，計算遍歷的次數得到鏈表的長度；
結合鏈表的長度和倒數的位置，可以得到正序要刪除節點的位置。
正向遍歷到該位置的前一個元素，進行刪除節點。
代碼示例：
public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode preResult = new ListNode();preResult.next = head;ListNode pre = preResult; // 臨時變量，找到要刪除的位置，進行刪除ListNode tail = head; // 尾指針，用于遍歷到尾部，找到鏈表的長度// 找到鏈表長度，計算得到要刪除的節點位置。int len = 0;while (tail!=null){len++;tail = tail.next;}int position = len - n; // 得到正序要刪除節點的位置下標// 找到位置，刪除元素for (int i = 0; i < position; i++) {pre = pre.next;}ListNode next = pre.next; // 找到要刪除的節點nextpre.next = next.next; // 斷開pre和next的指向關系，使pre指向enxt的后面節點next.next = null; // next與鏈表測地斷開return preResult.next;}
方法二：（利用棧的先進后出特性）
將所有的節點添加到棧中，那么倒數第N個節點，實際就是棧頂向下的第N節點。
依次出站N個元素，那么此時棧頂元素就是要刪除節點的前一個元素。此時回到鏈表直接刪除當前元素的下一個元素即可。
代碼示例：
public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode preResult = new ListNode();preResult.next = head;ListNode pre = preResult; // 中間變量，依次入棧操作用// 通過pre使鏈表元素依次入棧Stack<ListNode> stack = new Stack<>();while (pre!=null){stack.push(pre);pre = pre.next;}// 彈出元素，將目標位置元素和后面的元素全部彈出for (int i = 0; i < n; i++) {stack.pop();}// 此時，站頂元素為目標元素的前一個元素if (!stack.isEmpty()){pre = stack.peek();// 刪除目標元素pre.next = pre.next.next;} else {return new ListNode();}return preResult.next;}
方法三：（雙指針法）
利用兩個指針。
第一個還真向前遍歷N個元素，第二個指針指向起點。兩個指針之間的距離就是N。
之后，兩個指針一起向后移動，因為兩個指針距離N，當第一個指針達到尾部的時候，那么此時第二個節點剛好就是要刪除的節點。
實際為了刪除，我們要獲取的是目標刪除節點的前一個節點。所以第二個指針初始化應該是鏈表頭結點的前驅節點。
代碼示例：
public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);ListNode first = head;ListNode second = dummy;for (int i = 0; i < n; ++i) {first = first.next;}while (first != null) {first = first.next;second = second.next;}second.next = second.next.next;ListNode ans = dummy.next;return ans;}
向陽出發，Dare To Be！！！
)
