【Java】LeetCode 19. 删除链表的倒数第N个节点_java单向链表删除倒数第n节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先想到的肯定是把所有节点遍历一遍求出链表长度，然后就能知道要删除的节点在链表中正向的位置，然后再删除即可。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null)
            return head;
        int l=1;
        ListNode flag=head;
        while(flag.next!=null){
            l++;
            flag=flag.next;
        }
        if(l==n)
            return head.next;
        flag=head;
        l=l-n-1;
        for(int i=0;i<l;i++){
            flag=flag.next;
        }
        flag.next=flag.next.next;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

还可以这么想：倒数第N个节点就是距离最后一个节点N-1的节点

双指针，一个指针先拉开n的距离（用于测距），另一个指针需要指向待删除节点的父节点（用于删除）

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode flag1=head;
        for(int i=0;i<n-1;i++){
            flag1=flag1.next;
        }
        if(flag1.next==null){
            return head.next;
        }
        ListNode flag2=head;
        flag1=flag1.next;
        while(flag1.next!=null){
            flag1=flag1.next;
            flag2=flag2.next;
        }
        flag2.next=flag2.next.next;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

满足题设所说的一次遍历？

有点迷惑，两种解法都是从头到尾走一遍，从头到删除节点的父节点走一遍，区别只在于，第一种实现是一个指针走两遍，而第二种实现是两个指针一起走，实际上本质都一样吧（我觉得）

到底所谓一次遍历，优化在了哪里