leedcode【19】. 删除链表的倒数第 N 个结点—

leedcode【19】. 删除链表的倒数第 N 个结点——Java解法

Problem: 19. 删除链表的倒数第 N 个结点

思路
解题方法
复杂度
Code
性能

思路

如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

分为如下几步：

定义fast指针和slow指针，初始值为虚拟头结点，如图：
fast首先走n + 1步，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
fast和slow同时移动，直到fast指向末尾，如图：
删除slow指向的下一个节点，如图：

解题方法

双指针法

复杂度

时间复杂度:

O(n)

空间复杂度:

O(1)

Code

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);//虚拟节点，指向头节点
        dummy.next = head;
        ListNode fastNode = dummy;// 快指针
        ListNode lowNode = dummy;//慢指针
        for(int i=0; i <= n; i++){ //快慢指针相差n个节点
            fastNode = fastNode.next;
        }

        while(fastNode!=null){ //快慢指针向后移，直到快指针到链表末尾节点
            fastNode = fastNode.next;
            lowNode = lowNode.next;
        }
        //删除慢节点所指节点
        if(lowNode.next != null){
            lowNode.next = lowNode.next.next;
        }
        return dummy.next;
    }
}