LeetCode题解—删除链表倒数第n个结点-阿里云开发者社区

LeetCode题解—删除链表倒数第n个结点

2022-05-14 90

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 今天继续说链表常见问题中的——删除链表倒数第n个结点

前言

今天继续说链表常见问题中的——删除链表倒数第n个结点：

单链表反转
两个有序的链表合并
删除链表倒数第n个结点
求链表的中间结点
链表中环的检测

题目：删除链表倒数第n个结点

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

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

示例 1：输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：输入：head = [1], n = 1 输出：[]

示例 3：输入：head = [1,2], n = 1 输出：[1]

解法一

首先容易想到的办法就是想数组一样，遍历链表找到那个要被删除的结点，所以先解决两个问题：

1、获取链表的总长度

public int getLength(ListNode head){
        int n=0;
        while(head!=null){
            n++;
            head=head.next;
        }
        return n;
    }

2、找到结点之后，怎么删除。

其实就是把next指向跨过去要删除的结点就行了。

tempNode.next=tempNode.next.next;

但是，上述这个方法是删除的tempNode.next结点，如果我们要删除tempNode本身这个结点，那么就要把一开始的结点提前到第一个结点之前。

比如我们要删除链表的第一个结点，如果你本身的指针就指向第一个结点，那么通过上面这个删除方法就永远删除不了第一个结点了。

所以要把指针提前到第一个结点之前。

所以，综上所述，我们得出以下解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length=getLength(head);
        //新建一个新的链表结点指向head头结点，也就是上面要注意的特殊情况
        ListNode lastNode=new ListNode(0,head);
        ListNode tempNode=lastNode;
        for(int i=0;i<length-n;i++){
            tempNode=tempNode.next;
        }
        tempNode.next=tempNode.next.next;
        return lastNode.next;
    }
    public int getLength(ListNode head){
        int n=0;
        while(head!=null){
            n++;
            head=head.next;
        }
        return n;
    }
}

时间复杂度

用到了遍历、时间复杂度为O(n)

空间复杂度

只用到几个单独的链表结点，所以空间复杂度为O(1)

解法二

再想想，可不可以不计算链表长度呢？也就是题目上所说的进阶解法，用一次扫描。

再链表中，有一种常用的方法，叫做快慢指针，意思就是用到两个速度不同的指针解决一些问题。

比如这个题中，我们使用一个快指针一个慢指针，并且让快指针快n个结点，然后两个指针一直往后移动。当快指针移动到结尾，那么慢指针的位置就是我们要删除的结点了。

当然，这里也要考虑到当前结点被删除的情况，所以要把开始结点提前到链表之前。

public ListNode removeNthFromEnd(ListNode head, int n) {
 //提前链表
        ListNode LastNode=new ListNode(0,head);
        ListNode FirstNode=LastNode;
        ListNode SecondNode=head;
        for(int i=0;i<n;i++){
            SecondNode=SecondNode.next;
        }
        while(SecondNode!=null){
            FirstNode=FirstNode.next;
            SecondNode=SecondNode.next;
        }
        FirstNode.next=FirstNode.next.next;
        return LastNode.next;
    }