题目:删除链表倒数第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]
首先容易想到的办法就是想数组一样,遍历链表找到那个要被删除的结点,所以先解决两个问题:
public int getLength(ListNode head){
int n=0;
while(head!=null){
n++;
head=head.next;
}
return n;
}
其实就是把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;
}
时间复杂的为O(n)
空间复杂度为O(1)
还有其他的解法,比如用到栈先进后出
的原则,先把所有链表数据入栈,然后出栈n个数。剩下的栈顶就是要删除结点的前驱结点了,然后调用上述的删除结点方法,就可以删除要删除的下个结点了。
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/