LeetCode-19

题目

结果

代码

通过链表长度定位

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 计算长度
        int length = length(head);
        // 特殊情况
        if (length == n) {
            return head.next;
        }
        
        // 移动指针
        ListNode p = head;
        int index = length - n - 1;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        
        // 删除节点
        p.next = n == 1 ? null : p.next.next;
        return head;
    }

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

入栈再出栈

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 添加一个头节点
        ListNode trueHead = new ListNode(0);
        trueHead.next = head;
        // 入栈
        Deque<ListNode> stack = new LinkedList<>();
        ListNode p = trueHead;
        while (p != null) {
            stack.push(p);
            p = p.next;
        }

        // 出栈
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        // 删除节点
        ListNode pre = stack.peek();
        pre.next = pre.next.next;
        return trueHead.next;
    }
}

快慢指针

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode trueHead = new ListNode(0);
        trueHead.next = head;
        ListNode fast = trueHead, slow = trueHead;
        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 trueHead.next;
    }
}

复杂度

通过链表长度定位

时间复杂度：O（n）

空间复杂度：O（1）

借助栈

时间复杂度：O（n）

空间复杂度：O（n）

快慢指针

时间复杂度：O（n）

空间复杂度：O（1）