问题描述
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
解决思路(2019-12-06)
- set a dummy node
- set slow node and fast node, and they interval is n
- move slow and fast node simultaneously, until fast.next is null. now the slow move the the previous node of nth node of the end
- connect slow and slow.next.next node, which is the next node of nth node of the end
- disconnect the nth node and it’s next node
- return the dummy.next(which is the head node of original ListNode)
问题解惑
最后我提供了两种方法连接节点，第一种方法，断的干净一点，把要去掉的节点的下一个节点，置为了null。但是要注意slow和fast紧挨着的情况，比如list=[1], n = 1；第二个，方法更直接一点，虽然没有彻底 处理完，但完全不影响结果。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//1. set a dummy node
//2. set slow node and fast node, and they interval is n
//3. move slow and fast node simultaneously, until fast.next is null.
//now the slow move the the previous node of nth node of the end
//4. connect slow and slow.next.next node, which is the next node of nth node
//of the end
//4. disconnect the nth node and it's next node
//5. return the dummy.next(which is the head node of original ListNode)
ListNode dummy = new ListNode(0);
dummy.next = head;
//corner case
if(head == null) return null;
ListNode slow = dummy;
ListNode fast = dummy;
//move fast node, make the interval of them is n
for(int i = 0; i < n; i++){
fast = fast.next;
}
while(fast.next!=null){
slow = slow.next;
fast = fast.next;
}
if(slow.next != fast){
ListNode temp = slow.next.next;
slow.next.next = null;
slow.next = temp;
}else{
slow.next = null;
}
//another more concise way as follows:
//slow.next = slow.next.next;
return dummy.next;
}
}
效率探究
时间复杂度：O(n)
空间复杂度：O(n)
解决思路(2019-07-14)
方法很取巧，拿着纸和笔过一遍这个过程，知道这个对就行，但别问我为什么对。先建立一个dummy,放在head之前，slow和fast等于dummy。然后fast先移动n次结束，然后fast和slow一起走，直到fast走到最后一个（即fast.next == null）为止，此时slow.next指向的就是要删除的节点，将slow.next.next赋给slow.next就完成了删除倒数第n个节点的操作。（这就是对的，别问什么，问就是解法牛逼，beats率双一百）。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for(int i = 0; i < n; i++){
fast = fast.next;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
效率探究
时间复杂度：O(n^2)
空间复杂度：O(n^2)
