Algorithm Remove Nth Node from End of list

Description

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.

Submission

package com.cctoken.algorithm;


/**
 * @author chenchao
 */
public class RemoveNthNode {

  public static void main(String[] args) {
    ListNode head = new ListNode(1);
    ListNode res = new RemoveNthNode().removeNthFromEnd(head, 1);
    if (res != null) {

    }
  }

  public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) {
      return null;
    }
    ListNode start = new ListNode(0);

    ListNode fast = start;
    ListNode slow = start;
    slow.next = head;
    for (int i = 0; i < n; ++i) {
      fast = fast.next;
    }
    while (fast.next != null) {
      fast = fast.next;
      slow = slow.next;
    }
    slow.next = slow.next.next;
    return start.next;
  }


  public static class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
    }
  }
}

Solution

去除掉一个链表的倒数第N个节点。链表的特性决定了必须要遍历完整的链表才能知道各个node的具体位置。
拿到这道题的第一个思路是遍历的时候存入栈中，出栈的时候就知道倒数第N个节点是哪个，只要将此节点移除即可。但是考虑到这样的流程对
空间的占用肯定会很高，所以思路转为直接在遍历的时候，不存储就能达到移除的目的
利用快慢指针，使两者的间隔始终为N，那么当快指针到达链表的末端时，此时慢指针正好处于倒数第N+1个，此时将慢指针的下一个节点给移除即可。
然后最后的结果就是 start.next 即可，start.next 是用来标记一个链表的头

image.png