[leetcode]19. Remove Nth Node From End of List删除链表倒数第N个节点

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

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.

Follow up:

Could you do this in one pass?

题意： 删除链表倒数第N个节点

Solution1: Two Pointers(fast and slow)

1. Let fast pointer to move n steps in advance, making sure there is n steps gap between fast and slow 

2. Move fast and slow pointer together until fast.next == null

 

code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

/*
Time: O(n)
Space: O(1)
*/
class Solution {
      public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;

        for (int i = 0; i < n; i++)  // fast先走n步
            fast = fast.next;

        while(fast.next != null) { // fast和slow一起走
            slow = slow.next;
            fast = fast.next;
        }
        //直接skip要删除的节点
        slow.next = slow.next.next;  // 思考为何不能写成 slow.next = fast;
        return dummy.next;
    }
}