RemoveNthNodeFromEndOfList [source code]
public class RemoveNthNodeFromEndOfList {
static
/******************************************************************************/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int len = 1;
ListNode slow = head, fast = head, dummy = new ListNode (0), slow_prev = dummy;
slow_prev.next = slow;
while (fast.next != null) {
fast = fast.next;
if (len < n)
len++;
else {
slow_prev = slow;
slow = slow.next;
}
}
slow_prev.next = slow.next;
slow.next = null;
return dummy.next;
}
}
/******************************************************************************/
public static void main(String[] args) {
RemoveNthNodeFromEndOfList.Solution tester = new RemoveNthNodeFromEndOfList.Solution();
int[][] inputs = {
{1}, {1}, {},
{1, 2}, {1}, {1},
{1,2,3,4,5}, {2}, {1,2,3,5},
{1,2}, {2}, {2},
};
for (int i = 0; i < inputs.length / 3; i++) {
ListNode head = ListNode.buildListNode (inputs[3 * i]);
int n = inputs[3 * i + 1][0];
ListNode ans = ListNode.buildListNode (inputs[3 * i + 2]);
String ans_str = ListNode.serialize (ans);
String input_str = ListNode.serialize (head);
System.out.println (Printer.separator ());
ListNode output = tester.removeNthFromEnd (head, n);
String output_str = ListNode.serialize (output);
System.out.printf ("%s and %d -> %s, expected: %s\n",
input_str, n, Printer.wrapColor (output_str, output_str.equals (ans_str) ? "green" : "red"), ans_str
);
}
}
}
这几天做题有点不喜欢开计时器了, 要及时纠正一下这个坏习惯. 你可以这样想, 开这个计时器并不是真的指望你最后能够写的有多快, 其实很多时候更多的目的是为了防止你在一题上面浪费太多的时间;
笨办法肯定是走两遍, 不过这种估计面试的时候过不了;
以前说过LinkedList问题, 于是不决就invert, 是可以做的, 不过还是做不到One pass;
语言描述笨办法呢? cache head node, then go to end, then go backwards, point to the Nth node, then remove it, the return head. Why it doesn't work? You have to do two passes. 好像也没有找到什么突破点;
想了10分钟没想法, 感觉是个脑筋急转弯的题目, 懒得想了;
看了editorial之后自己想写一个; 一个小提示, 写while循环的时候不要害怕用break, 真的, 别有洁癖.
这题就最好要有一个dummy; 因为最后test4故意把head给delete掉了;
最后是做出来了, 速度是17ms (14%).
回头看看editorial写的实际上没有我的好, 他还是用了两个循环, 我用一个类似sliding window的思路, 一个循环就搞定了;
editorial
Approach #1 (Two pass algorithm)
public ListNode removeNthFromEnd(ListNode head, int n) {
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;
}
转换成index from head, 然后找就行了; LinkedList题目的一个要点就是这个方向性要始终放在心上; 不过这个不是1pass的算法;
Approach #2 (One pass algorithm)
Algorithm
The above algorithm could be optimized to one pass. Instead of one pointer, we could use two pointers. The first pointer advances the list by
n+1 steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by
n nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the
nth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node's next next node.
只能说天秀. 我只想到了一个我唯一会的快慢指针, 就是速度的差别; 但是这里这个真的是活学活用, 无话可说;
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
貌似答案里面很多人认为这个问题的要求很无聊, 因为实际上1pass的做法每一个iteration里面的increment反而多一点, 最后跟2pass的是差不多的; 不过我觉得这种人就是纯粹没有get到这个问题的点; 有时候, traverse一个LinkedList是可以很expensive的, 相反increment并不是衡量runtime的唯一标准;
@TMS said in Simple Java solution in one pass:
A one pass solution can be done using pointers. Move one pointer fast --> n+1 places forward, to maintain a gap of n between the two pointers and then move both at the same speed. Finally, when the fast pointer reaches the end, the slow pointer will be n+1 places behind - just the right spot for it to be able to skip the next node.
Since the question gives that n is valid, not too many checks have to be put in place. Otherwise, this would be necessary.
注意他这句话, 这个其实是我目前的一个弱项, 我代码写完习惯性就直接想提交了; 真正面试的时候, 做完了, 甚至是开始写之前, 一定要先跟面试官把corner case都聊开; 之前做题的时候碰到过对Corner Case的理解不合理不是一次两次了;
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;
}
算法本身跟editorial是一个意思;
discussion里面也有很多喷这个题目的:
@arun6 said in Simple Java solution in one pass:
Yes. The problem is meaningless. The funny thing is your answer is the one which is close to being correct. But it has just one upvote.
Two pointer technique is a good technique which can be used in other places like finding cycle in the list. But this problem is particularly worded to force people to think that two pointer technique can give the answer in one pass.
c++写法:
@taotaou said in My short C++ solution:
class Solution
{
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode** t1 = &head, *t2 = head;
for(int i = 1; i < n; ++i)
{
t2 = t2->next;
}
while(t2->next != NULL)
{
t1 = &((*t1)->next);
t2 = t2->next;
}
*t1 = (*t1)->next;
return head;
}
};
有人认为他这个算法有内存泄露, 不过我感觉这个东西实际面试的时候还是问清楚比较好, 毕竟这个函数本身也就是一个component, 未必要你释放;
仔细想想, 这个题目的题型其实不陌生, 这个是一个LinkedList里面要完成reversed order的题目, 这个我们以前还总结过另外一个方法, 还有印象吗?
没错, 就是用recursion完成倒序.
@tim14 said in My short C++ solution:
Thanks for sharing.
Here is a recursive solution.code:
int countAndRemove(struct ListNode *node, int n){
//Once the stack frame reaches the tail, counting starts.
if(!node->next) return n-1;
int NumOfNodesLeft = countAndRemove(node->next, n);
//If there are exactly n nodes in the rest of the list, delete next node.
if(NumOfNodesLeft == 0) node->next = (node->next)->next;
//Count decremented.
return NumOfNodesLeft - 1;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
return (countAndRemove(head, n) == 0)? head->next : head;
}
The idea is based on how function call, namely pushing and popping stack frames, works.
i) Push as many stack frames as the size of linked list. so n is passed to the end (top frame). ii) As the last frame pops off, counting begins.Suppose there S nodes in the linked list.
The stack frames would be like the following:
===================================================
Sth stack: 1st node ( counting from the back ) n = n, NumOfNodesLeft = n, return n - 1.
===================================================
(S-1)th stack: 2nd node ( from the back ), n = n, NumOfNodesLeft = n - 1, return n - 2.
===================================================
:
===================================================
(S-n-1)th stack: 2nd node ( from the back ), n = n, NumOfNodesLeft = 0, return -1.
Only this frame does the deletion.
===================================================
:
===================================================
Second stack: (S-1)Th node ( counting from the back ), NumOfNodesLeft = n - (S -1), return n - (S-1) - 1.
===================================================
First stack: Sth node from the back / 1st node in the list, NumOfNodesLeft = n - S, return n - S - 1.
===================================================
下面的解释没怎么看了, again, 研究一个算法, 搞一个小例子先, 我直接用1,2,3和2来思考, 然后你就很容易的理解这里的思路了; 通过一个PostOrder的recursion, 先走到尽头, 然后直接counter--下去, 最后就完成了一个count from end的操作;
不过一个小的疑惑就是, 你说这个算不算1pass? 好像不好界定;
Stefan给出几个有趣的写法:
@StefanPochmann said in 3 short Python solutions:
Value-Shifting - AC in 64 ms
My first solution is "cheating" a little. Instead of really removing the nth node, I remove the nth value. I recursively determine the indexes (counting from back), then shift the values for all indexes larger than n, and then always drop the head.
class Solution:
def removeNthFromEnd(self, head, n):
def index(node):
if not node:
return 0
i = index(node.next) + 1
if i > n:
node.next.val = node.val
return i
index(head)
return head.next
这个应该还是比较好理解的一个recursion, 直接用[1,2,3,4], 2这个例子来帮助理解就行了; 脑子里visual recursion的时候, 从左到右有一个calling Stack, 然后每一个node是一个函数代码段, 然后大概提醒一下自己走到哪里了, 右边的返回值被放到了左边的什么变量里面;
Index and Remove - AC in 56 ms
In this solution I recursively determine the indexes again, but this time my helper function removes the nth node. It returns two values. The index, as in my first solution, and the possibly changed head of the remaining list.
class Solution:
def removeNthFromEnd(self, head, n):
def remove(head):
if not head:
return 0, head
i, head.next = remove(head.next)
return i+1, (head, head.next)[i+1 == n]
return remove(head)[1]
这个算法因为涉及到了modification, 所以不是特别好visual, 还是动笔算一下比较好;
不过还是可以借助上面visual的方法来笔算, 一个node的代码段可以用一个从上到下的trace来代表; 这样画起来应该还是很方便的;
动笔画了一下, 同样的例子, 可以看到他这个算法还是很聪明的, 对recursion的理解很深; 基本的套路就是当我们在3的时候, 我们发现3应该被删除, 这个时候就把3的next, 也就是4直接返回上去, 然后3的parent会把自己的next设置到4, 这样3就相当于被删除了, 这个是之前有一个delete题目用过的一个技巧;
n ahead - AC in 48 ms
The standard solution, but without a dummy extra node. Instead, I simply handle the special case of removing the head right after the fast cursor got its head start.
class Solution:
def removeNthFromEnd(self, head, n):
fast = slow = head
for _ in range(n):
fast = fast.next
if not fast:
return head.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
他这里避免dummy的方法也很直接聪明;
submission最优解, 14(65):
class Solution {
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;
}
}
Problem Description
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.
Difficulty:Medium
Total Accepted:223K
Total Submissions:652.5K
Contributor:LeetCode
Related Topics
linked listtwo pointers