题解 | #删除链表的倒数第n个节点#
删除链表的倒数第n个节点
https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6
方法一、计算链表长度
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
//思路：两次遍历，一次求链表长度，第二次删除节点
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
if (head==null)return null;
ListNode cur=head,pre=null,next=null;
int count=1;
while(cur.next!=null){
count++;
cur=cur.next;
}
cur=head;
int location=count-n;
//如果是删除第一个节点
if(location==0){
head=head.next;
return head;
}
while(location!=0){
pre=cur;
cur=cur.next;
next=cur.next;
location--;
}
pre.next=next;
cur=null;
return head;
}
}
方法2、快慢节点法import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
//思路：快慢节点，快节点比慢节点提前n个位置，
//这样当快节点到末尾时，慢节点所处的位置刚好是倒数第n个位置
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
if (head==null)return null;
ListNode slow=head,pre=null,next=null;
ListNode fast=head;
int i=0;
while(i++!=n&&fast!=null){
fast=fast.next;
}
//此时说明n==length，删除的是第一个元素
if(fast==null){
head=head.next;
return head;
}
while(fast!=null){
fast=fast.next;
pre=slow;
slow=slow.next;
next=slow.next;
}
pre.next=next;
slow=null;
return head;
}
}
投递七牛云等公司10个岗位