LeetCode笔记:19. Remove Nth Node From End of List
2023-03-15 23:20:41 时间
问题:
Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass.
大意:
给出一个链表,移除链表的倒数第n个节点并返回链表头。 例子, 给出链表: 1->2->3->4->5, 以及 n = 2. 在移除倒数第二个节点后,列表变为了 1->2->3->5。 注意: 给出的n一定是有效的。 尝试在一轮循环中做。
思路:
题目的难点在于你不知道遍历到第几个节点时是要删除的倒数第n个节点。
我的做法很笨,遍历一遍记录所有节点的值和位置,然后重新根据值和位置创建新的链表,跳过要删除的那个位置的节点,因为此时知道总节点数了就可以推出是第几个节点了。在操作时要注意一些特殊情况,比如只有一个节点时、删除头结点时要怎么处理。
代码(Java):
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int[] nodeVal = new int[100];
int[] nodeIndex = new int[100];
nodeVal[0] = head.val;
nodeIndex[0] = 0;
int index = 1;
while (head.next != null) {
head = head.next;
nodeVal[index] = head.val;
nodeIndex[index] = index;
index++;
}
ListNode newHead;
int begin = 0;
if (index == 1) return null;
else if (index == n) {
newHead = new ListNode(nodeVal[1]);
begin = 1;
} else newHead = new ListNode(nodeVal[0]);
ListNode tempNode = newHead;
for (int i = begin+1; i < index; i++) {
if (i != index - n) {
ListNode newNode = new ListNode(nodeVal[i]);
tempNode.next = newNode;
tempNode = newNode;
}
}
return newHead;
}
}
他山之石:
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode start = new ListNode(0);
ListNode slow = start, fast = start;
slow.next = head;
//Move fast in front so that the gap between slow and fast becomes n
for(int i=1; i<=n+1; i++) {
fast = fast.next;
}
//Move fast to the end, maintaining the gap
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
//Skip the desired node
slow.next = slow.next.next;
return start.next;
}
看一下这个巧妙的做法,他设了快慢两个标记,初始都在头结点,快的先往后遍历,遍历到与头结点相差为n的时候停止,然后快的和慢的一起往后走,直到快的走到了链表尾节点打止,这时候快慢两个节点间相差的节点数正好是n,也就是说慢的所在的下一个节点正好是要删除的节点,直接跳过去就可以了,一遍遍历完成,很棒。
相关文章
- Win7便笺、StikyNot.exe、打不开的解决办法、便签已停止启动
- 一览zookeeper3.6.0新特性
- 【算法千题案例】每日LeetCode打卡——75.字符串相加
- 到了弃用Redis-sentinel架构的时候了
- Git学习(三):操作分支常用命令
- pytorch-TensorFlow-线性回归
- java.beans.* 篇(2)Expression,Statement,Encoder,XmlEncoder,XmlDecoder使用案例
- Django笔记(一)setting.py里面配置的相关解释
- 千人围观!在本地客户端、连接Windows实例、远程云服务器(本地设备使用Windows操作系统)
- 蓝桥杯单片机定时器1的编码以及数码管的动态显示
- Consul1.7 多数据中心 新Hashicorp学习指南
- VPS使用ProxySU搭建节点服务器
- Django笔记(二)view.py里面方法返回的函数,render(),httpresponse()等其他渲染函数
- Git学习(四):GitHub远程库操作
- Illegal character in opaque part at index
- 图像处理之图像匹配
- Django笔记(八)view文件里面类的写法,和路由映射的思路
- dotnet OpenXML 读取 PPT 内嵌 xlsx 格式 Excel 表格的信息
- ML Visuals-神经网络画图神器
- Git学习(六):IDEA集成Git