每天一题LeetCode【第16天】

T19. Remove Nth Node From End of List【Medium】

题目

给定一个链表，从链表的末尾删除第n个节点并返回它的头。

例如，

   给出链表: 1->2->3->4->5,以及 n = 2.

   在移除了倒数第二个节点后, 链表变成了 1->2->3->5.

补充：

给出的 n 总是有效地

尝试把这题一遍过

思路

① 首先建议不明白链表的先了解一下链表

② 代码用start保存首节点，用fast和slow结合起来寻找到目标节点位置

③ 因为链表不能从后往前移动，也不知道长度，所以先把 fast 前移 n，保持 slow 和 fast 的差值，把 fast 移动到最后（也就是链表常用的 fast==null）,然后此时 slow 就能容易的定位到倒数第n个数

④ 链表常用去节点方式：slow.next = slow.next.next; 下面举个例子

链表 A->B->C  去掉B：A 放开 B 的尾巴，抓住 C 的尾巴

⑤ 具体看代码以及注释~

⑥ 有问题欢迎吐槽哈~

代码

代码取自 Top Solution，稍作注释

/**
 * 给出的ListNode的结构
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
   public ListNode removeNthFromEnd(ListNode head, int n) {
    //初始化一个 val=0 的 ListNode ,并赋给 start,slow,fast
    ListNode start = new ListNode(0);
    ListNode slow = start, fast = start;
    //把传入的链表赋给slow.next
    slow.next = head;
    //把 fast 往前移动 n,使得fast和slow相差n
    for(int i=1; i<=n+1; i++)   {
        fast = fast.next;
    }
    //把fast移动到最后一个, 保持slow一起移动，相差不变，此时slow就是从后往前n
    while(fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    //通过这句代码跳过中间的节点
    slow.next = slow.next.next;
    //start用来保存首节点，返回start.next就是首节点
    return start.next;
}
}  

补充

关于代码中的,debug了一下，slow 和 fast 的地址和 start 是一样，所以是传递地址的，在后面改了任一一个其他的也会改。

 ListNode start = new ListNode(0);
 ListNode slow = start, fast = start;

可以看到地址是相同的（哎这个应该是地址吧）~