删除链表的倒数第N个节点，并返回链表的头节点
JAVA乐园
共 1126字，需浏览 3分钟
·
2021-01-28 21:47
面试的时候遇到了一个笔试题，是leetcode的原题，原题的连接：
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
大概的内容：删除链表的倒数第N个节点，并返回链表的头节点。
一开始遇到这个题也是一脸懵，通过查看解题思路才了解到有几种解决方式：
单向项链表实现类：
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
0x01：两次循环求长度
实现思路：
1、先循环一遍链表，求出链表的长度L，倒数第N个节点就是从开头数第（L-N+1）个节点,将此节点的next指向下下节点就可以了。
在解题的过程中要添加一个亚节点（dummy）进行辅助（如:图1），D就是我们的亚节点。
代码：
ListNode dummy = new ListNode(0);//亚节点
dummy.next = head;
int length = 0;
ListNode first = head;
//通过移动头节点循环求出链表的长度
while(first != null){
length++;
first=first.next;
}
length -= n;//计算要删除节点位置
first = dummy;
while(length > 0){
length --;
first = first.next;
}
first.next = first.next.next;
return dummy.next;//返回头节点
0x02：双指针
实现思路：
1、定义两个指针同时指向我们的亚节点。
2、第一个指针节点向前移动N+1步，第二个指针保持不动，这时两个指针相隔N个节点的距离
3、同时移动两个指针保持恒定的距离，直到第一个指针到达最后一个节点。
4、这时第二个指针所指向的节点的下一个节点就是要删除的节点（倒数第N个节点），将第二个指针指向的节点的next指向下下个节点就完成了。
代码：
ListNode dummy = new ListNode(0);//亚节点
dummy.next = head;
ListNode first = dummy;//第一个指针
ListNode secound = dummy;//第二个指针
for(int i = 0; i//向前移动第一个之指针N+1步
first= first.next;
}
while(first != null){//同时移动第一个指针和第二个指针直到第一个指针指向null
first = first.next;
secound = secound.next;
}
secound.next = secound.next.next;
return dummy.next; 我们能看到方法二比方法一代码简洁一些，双指针也是算法题里面比较常用的解题方法。
仔细查看评论区我们又看到不错的解题思路，使用递归方法和特性实现
0x03：递归的特性
实现思路：
1、利用递归调用的特性先循环一遍链表，相当于用指针从链表头走到链表尾（如：图3-2）
2、递归调用在调用自身方法后面会倒叙的循环调用，相当于指针在从尾节点执行到头节点，这时在第N步将指针指向的节点的next指向下下个节点就完成了。
这里递归的特性和使用会在后面单独写一篇文章来说明。
代码：
public static ListNode removeNthFromEnd(ListNode head, int n) {
int pos = helper(head, n);
// 说明删除的是头节点
if(pos == n - 1) {
return head.next;
}
return head;
}
// 获取节点所在位置，逆序
public int helper(ListNode node, int n) {
if(node.next == null) {
return 0;
}
int pos = helper(node.next, n) + 1;
if(pos == n) {
node.next = node.next.next;
}
return pos;
}
source：https://www.cnblogs.com/stevewys/articles/13252439.html
喜欢，在看
评论