給定一個鏈表，刪除鏈表的倒數第?n?個節點，并且返回鏈表的頭結點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.當刪除了倒數第二個節點后，鏈表變為 1->2->3->5.

說明：

給定的?n?保證是有效的。

public class Solution {public static void main(String[] args) {// 1 -> 2 -> 3 -> 4 -> 5ListNode 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 newRoot = removeNthFromEnd1(node1, 2);// ListNode newRoot = removeNthFromEnd2(node1, 3);while (newRoot != null) {System.out.println(newRoot.val);newRoot = newRoot.next;}}// 方法一：雙指針private static ListNode removeNthFromEnd1(ListNode head, int n) {ListNode first = head;ListNode second = head;for (int k = 0; k < n; k++) { // 讓前一個指針先走n步first = first.next;}if (first == null) {return head.next; // 鏈表的長度剛剛好等于n，頭結點為要刪除的節點}while (first.next != null) { // 兩個指針同時向后走，直到前一個指針走到鏈表最后一個節點的nextfirst = first.next;second = second.next;}second.next = second.next.next; // 將要刪除節點的前一個節點指向要刪除節點的后一個節點return head;}// 方法二：借助棧private static ListNode removeNthFromEnd2(ListNode head, int n) {ListNode temp = head;Stack<ListNode> stack = new Stack<>();while (temp != null) { // 先用棧存儲整個鏈表stack.push(temp);temp = temp.next;}if (stack.size() == n) { // 如果棧的大小剛剛好等于n，頭結點為要刪除的節點return head.next;}for (int k = 0; k <= n; k++) { // 逐個彈棧，相當于鏈表從后向前遍歷ListNode peek = stack.pop();if (k == n - 2) { // 保存要刪除的節點的后一個節點temp = peek;}if (k == n) { // 將要刪除節點的前一個節點指向要刪除節點的后一個節點peek.next = temp;}}return head;}}class ListNode {int val;ListNode next;ListNode(int x) {val = x;}
}

?