Given a linked list, remove the nth node from the end of list and return its head.
For example,

Given linked list: 1->2->3->4->5, and n = 2. 
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:Given n will always be valid.Try to do this in one pass
給定一個鏈表，移除從鏈表末尾起的第n個節(jié)點，并返回鏈表head

方法一

算法分析

• 首先需要一個dummy節(jié)點，指向鏈表head位置，主要是為了在鏈表長度為1時簡化代碼。
• 要刪除的節(jié)點在L-n+1位置（L為鏈表長度）。
• 找到第L-n個節(jié)點，指向L-n+2個節(jié)點。

答案

/**
 * 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) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = head;
        int length = 0;//鏈表長度
        while (current != null) {
            length ++;//尋找鏈表長度
            current = current.next;
        }
        length = length - n;//到要被刪除位置的鏈表節(jié)點的前一個
        current = dummy;
        while (length > 0) {
            length --;
            current = current.next;
        }
        current.next = current.next.next;//將被刪除的節(jié)點前一個節(jié)點指向被刪除節(jié)點的下一個節(jié)點
        return dummy.next;
    }
}

方法二

算法分析

• first、second兩個節(jié)點指向head
• 移動first節(jié)點到與second相差n個節(jié)點的位置
• 同時移動first、second直到first為null
• 此時second的下一個節(jié)點是為要刪除的節(jié)點

答案

/**
 * 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) {
        ListNode dummy = new ListNode(0);
        ListNode first = dummy;
        ListNode second = dummy;
        dummy.next = head;
        
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;//將first移到與second相差n個節(jié)點
        }
        while (first != null) {//first和second同時移動，直到first到最后一個節(jié)點的下一個節(jié)點
            first = first.next;
            second = second.next;
        }
        
        second.next = second.next.next;
        return dummy.next;
    }
}

參考

LeetCode