题解 | #删除链表的倒数第n个节点#

import java.util.List;
import java.util.Stack;

/**

• 删除链表的倒数第n个结点
• /
  public class RemoveNthFromEnd {
  public static void main(String[] args) {

// ListNode node5 = new ListNode(5, null);
// ListNode node4 = new ListNode(4, node5);
// ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, null);
ListNode head = new ListNode(1, node2);

    ListNode pre = removeNthFromEndByFastSlowPoint(head, 2);

}

/**
 * 通过两个stack实现
 *
 * @param head
 * @param k
 * @return
 */
public static ListNode removeNthFromEndBystack(ListNode head, int k) {

    Stack<Integer> stack1 = new Stack<>();

    while (head != null) {
        stack1.add(head.val);
        head = head.next;
    }

    Stack<Integer> stack2 = new Stack<>();

    int size = stack1.size();

    for (int i = 1; i <= size; i++) {
        Integer tmp = stack1.pop();
        if (i != k) {
            stack2.add(tmp);
        }
    }
    ListNode newHead = new ListNode(0, null);
    ListNode pre = newHead;
    while (!stack2.isEmpty()) {
        newHead.next = new ListNode(stack2.pop(), null);
        newHead = newHead.next;
    }

    return pre.next;
}

/**
通过快慢指针 fast指针先确定出链表的长度
*/

public static ListNode removeNthFromEndByFastSlowPoint(ListNode head, int n) {
    ListNode fast = head;
    ListNode slow = head;
    ListNode pre = slow;

    int length = 0;

    while (fast != null) {
        fast = fast.next;
        length++;
    }
    //特殊情况 链表就一个元素
    if (length == 1 && n == 1) {
        return null;
    }
    // 特殊情况，n和链表的长度相等 就是删除链表的第一个元素
    if (length == n) {
        head  = head.next;
        return head;
    }
    for (int i = 1; i < length; i++) {
        if (i == length - n) {
            slow.next = slow.next.next;
            break;
        } else {
            slow = slow.next;
        }
    }
    return pre;

}


static class ListNode {
    int val;
    ListNode next = null;

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

}