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

题目说明

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

• 示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

代码实现

一次遍历

public class RemoveNthFromEnd {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
       // 虚拟头结点，返回结果就返回头结点的下一个结点就好
       ListNode node  = new ListNode(-1);
        ListNode p = node;
        node.next = head;
        ListNode temp  = node;
        for (int i = 0; i <n; i++) {
            if(temp.next!=null){
                temp = temp.next;
            }else {
                return null;
            }
        }

        while (temp.next!=null){
            temp = temp.next;
            node = node.next;
        }
        temp = node.next;
        node.next = temp.next;
        temp.next =null;
        return p.next;
    }
}

复杂度分析

• 时间复杂度：O(L)，该算法对含有 L 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)。

• 空间复杂度：O(1)