Leetcode17-删除链表的倒数第n个节点

方法1：统计链表长度

1.思路：要删除链表某个节点，只需要统计链表长度，当cur指向倒数第n+1个元素时，删除倒数第n个元素即可。需要注意的是，当链表只有一个元素时，为了删除元素，需要设置一个哑节点。最后返回dummy.next即可。

2.代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //设置哑节点，方便只有一个元素时删除节点。
        ListNode dummy = new ListNode(0, head);
        int len = 0;
        ListNode cur = head;
        //统计链表长度
        while (cur != null){
            len++;
            cur = cur.next;
        }
        int i = 1;
        cur = dummy;//cur从哑节点开始
        //从哑节点开始遍历，链表长度为n+1。最后cur指向倒数n+1个位置
        while (cur != null && i < len + 1 - n){
            i++;
            cur = cur.next;
        }
        //删除第n个节点
        cur.next = cur.next.next;
        return dummy.next;
    }
}

复杂度分析：

时间复杂度：0(n)

空间复杂度：0(1)

方法2：双指针

1.思路：要删除链表某个节点，只需要统计链表长度，当cur指向倒数第n+1个元素时，删除倒数第n个元素即可。需要注意的是，当链表只有一个元素时，为了删除元素，需要设置一个哑节点。最后返回dummy.next即可。

最开始没设置哑节点，无法处理有两个元素的情况。因为要多

2.代码：

        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy, right = dummy;
        int count = 0;
        //right比left先走n + 1步
        //当right指向null时，left指向倒数n + 1个元素
        while(count <= n){
            count++;
            right = right.next;
        }
        while (right != null){
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return dummy.next;

复杂度分析：

时间复杂度：0(n)

空间复杂度：0(1)