Leetcode算法Java全解答--19. 删除链表的倒数第N个节点.md

Posted by lizhao on 07-09,2019

Leetcode算法Java全解答--19. 删除链表的倒数第N个节点

[toc]

题目

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

说明: 给定的 n 保证是有效的。

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

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.

想法

  1. 空间换时间的做法

用一个长度为n+1的数组接收节点

不过需要实时更新数组,有点复杂

时间复杂度为n,空间复杂度为n 2. 遍历2次法

先循环一次,算出长度,不过扫描了2次,

不符合题目

复杂度n/1

  1. 双指针法

搞2个指针,让AB指针中间间隔为n+1,这样A到末尾的时候,B的下一个节点刚好就是要删掉的东西

复杂度n/1

结果

超过99%的测试案例

时间复杂度:n

空间复杂度:1

总结

遇到链表没有第一时间想到双指针

空间换时间,虽然可以做出来,但是很操蛋

代码

我的答案

   /*
 * Copyright (C), 2015-2018
 * FileName: Solution019
 * Author:   zhao
 * Date:     2018/11/19 21:11
 * Description: 19. 删除链表的倒数第N个节点
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈19. 删除链表的倒数第N个节点〉
 *
 * @author zhao
 * @date 2018/11/19 21:11
 * @since 1.0.1
 */
public class Solution019 {

    /**************************************
     * 题目
     给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
     示例:
     给定一个链表: 1->2->3->4->5, 和 n = 2.

     当删除了倒数第二个节点后,链表变为 1->2->3->5.
     说明:
     给定的 n 保证是有效的。
     进阶:
     你能尝试使用一趟扫描实现吗?
     **************************************/

    /**************************************
     *
     * 想法:
     *          1. 空间换时间的做法
     *              用一个长度为n+1的数组接收节点
     *              不过需要实时更新数组,有点复杂
     *              时间复杂度为n,空间复杂度为n
     *          2. 遍历2次法
     *              先循环一次,算出长度,不过扫描了2次,不符合题目
     *          3. 双指针法
     *              搞2个指针,让AB指针中间间隔为n+1,这样A到末尾的时候,B的下一个节点刚好就是要删掉的东西
     *
     * 我的做法
     *      超过99%的测试案例
     *      时间复杂度:n
     *      空间复杂度:1
     * 代码执行过程:
     *
     * 总结:
     *      遇到链表没有第一时间想到双指针
     *      空间换时间,虽然可以做出来,但是很操蛋
     *
     * ***********************************/
    public ListNode removeNthFromEnd(ListNode head, int n) {

        if (head == null || n == 0) {
            return head;
        }

        ListNode ANode = head;
        ListNode BNode = head;

        for (int i = 0; i < n; i++) {
            ANode = ANode.next;
        }
        while (ANode == null) {
            ANode = ANode.next;
            BNode = BNode.next;
        }

        if (n == 1) {
            BNode.next = null;
        } else {
            BNode.next = BNode.next.next;
        }

        return head;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public void better() {
    }

}

大佬们的答案

/**************************************
 * 比我好的答案 better
 * ***********************************/
public ListNode better(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length = 0;
    ListNode first = head;
    while (first != null) {
        length++;
        first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
        length--;
        first = first.next;
    }
    first.next = first.next.next;
    return dummy.next;
}

测试用例

@Test
public void test019() {
    // 创建测试案例
    ListNode listNode1 = new ListNode(1);
    ListNode listNode2 = new ListNode(2);
    ListNode listNode3 = new ListNode(3);
    ListNode listNode4 = new ListNode(4);
    ListNode listNode5 = new ListNode(5);
    listNode1.next = listNode2;
    listNode2.next = listNode3;
    listNode3.next = listNode4;
    listNode4.next = listNode5;
    int n1 = 2;

    // 测试案例期望值
    ListNode expResult1 = new ListNode(1);
    ListNode expResult12 = new ListNode(2);
    ListNode expResult13 = new ListNode(3);
    ListNode expResult15 = new ListNode(5);
    expResult1.next = expResult12;
    expResult12.next = expResult13;
    expResult13.next = expResult15;

    // 执行方法
    Solution019 solution019 = new Solution019();
    ListNode result1 = solution019.removeNthFromEnd(listNode1, n1);

    // 判断期望值与实际值
    Assert.assertEquals(expResult1.toArray(), result1.toArray());
}

其他

代码托管码云地址:https://gitee.com/lizhaoandroid/LeetCodeAll.git

查看其他内容可以点击专栏或者我的博客哈:https://blog.csdn.net/cmqwan

“大佬们的答案” 标签来自leetcode,侵权请联系我进行删改

如有疑问请联系,联系方式:QQ3060507060