LeetCode题解之如何删除链表倒数第n个结点

这篇文章主要讲解了“LeetCode题解之如何删除链表倒数第n个结点”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“LeetCode题解之如何删除链表倒数第n个结点”吧!

创新互联建站主要从事网站制作、成都做网站、网页设计、企业做网站、公司建网站等业务。立足成都服务石鼓,十多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

题目:删除链表倒数第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;     }

感谢各位的阅读,以上就是“LeetCode题解之如何删除链表倒数第n个结点”的内容了,经过本文的学习后,相信大家对LeetCode题解之如何删除链表倒数第n个结点这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!

文章题目:LeetCode题解之如何删除链表倒数第n个结点
文章URL:https://www.cdcxhl.com/article14/iidoge.html

成都网站建设公司_创新互联,为您提供Google网页设计公司域名注册手机网站建设网站排名用户体验

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

营销型网站建设