Remove Nth Node From End of List

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

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.

 

Note

The minimum number of nodes in list is n.

Challenge

O(n) time

 

SOLUTION:

笨方法就是走一遍，确定list的长度，然后再走一遍len－n的长度就行了，但是要求O(n)的话就要用到两个指针，第一个指针先走n步，第二个再走，当第一个指针已经到尾的时候，第二个指针跟尾自然相差n个，但是删除list的node的时候，要记录node前面的点，才能进行删除操作。

代码：

/** * Definition for ListNode. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int val) { *         this.val = val; *         this.next = null; *     } * } */ public class Solution {    /**     * @param head: The first node of linked list.     * @param n: An integer.     * @return: The head of linked list.     */    ListNode removeNthFromEnd(ListNode head, int n) {        if (head == null || n < 1){            return head;        }        ListNode dummy = new ListNode(0);        dummy.next = head;        ListNode preDel = dummy;        for (int i = 0; i < n; i++){            if (head != null){                head = head.next;            }        }        while (head != null){            head = head.next;            preDel = preDel.next;        }        preDel.next = preDel.next.next;        return dummy.next;    }}