LeetCode19-删除链表的倒数第N个结点

直接删除

//计算链表长度法
public ListNode removeNthFromEnd(ListNode head, int n) {
    //创建头结点
    ListNode dummy = new ListNode(0, head);
    //计算长度
    //head 从0开始
    int length = getLength(head);
    //头结点从1开始
    ListNode cur = dummy;
    for (int i = 1; i <= length - n ; ++i) {
        cur = cur.next;
    }
    cur.next = cur.next.next;
    return dummy.next;
}

public int getLength(ListNode head) {
    int length = 0;
    while (head != null) {
        head = head.next;
        ++length;
    }
    return length;
}

使用辅助栈

//使用辅助栈
public ListNode removeNthFromEnd1(ListNode head, int n) {
    //创建头结点
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    Stack<ListNode> stack = new Stack<>();
    ListNode cur = dummyHead;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    for (int i = 1; i <= n; i++) {
        stack.pop();
    }
    ListNode peek = stack.peek();
    peek.next = peek.next.next;
    return dummyHead.next;
}