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

一、题目

请输入图片描述

二、两种解题思路

①方法一:二次遍历法

1)方法介绍:

   时间复杂度:O(2n)

   空间复杂度:O(n)

2)核心代码:

public static ListNode removeNthFromEnd(ListNode head, int n) {
        int count = 0;
        ListNode cur = new ListNode(0);
        cur.next = head;
        ListNode first = head;
        while ( first!= null) {
            count++;
            first = first.next;
        }
        count -= n;
        first=cur;
        while (count > 0) {
            count--;
            first = first.next;
        }
        first.next = first.next.next;
        return cur.next;
    }

②方法二:快慢n步指针

1)方法介绍:

   时间复杂度:O(n)

   空间复杂度:O(n)

2)核心代码:

    
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

三、LeetCode成功截图
请输入图片描述

四、感想

加油,加油,再加油,坚持,坚持,再坚持。

Last modification:October 23rd, 2019 at 10:42 pm
如果觉得我的文章对你有用,请随意赞赏

2 comments

  1. xinye

    秀啊我艹

  2. 书生

    加油,坚持

Leave a Comment