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

示例:

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

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

说明:

给定的 n 保证是有效的。

进阶:

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


这个题可以使用双指针,befaft ,让 bef 先于 aft 指针 n 个元素,如果此时bef指针指向了null,即说明指向了末尾即n==链表长度,所以删除的是链表的头节点,此时直接返回head.next.
另一种情况,两个指针同时移动,当 bef 指针移向尾节点时, aft 指针刚好移动的要删除节点的前一个节点.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode bef = head;
        ListNode aft = head;
        for (int i = 0; i < n; i++) {
            bef = bef.next;
        }
        //链表的长度刚好是n,即删除头节点
        if (bef==null){
            return head.next;
        }
        while (bef.next!=null){
            bef = bef.next;
            aft = aft.next;
        }
        aft.next = aft.next.next;
        return head;

    }
}

标签: leetcode, java

添加新评论