题解 | # 删除链表的倒数第n个节点#

思路

同#链表中倒数最后k个结点#,使用快慢指针。

快指针比慢指针先n步，快慢指针同步前进，快指针碰到null时，慢指针就是待删除结点，比起上一题，需要再维护一个pre结点，记录slow指针前面的结点，最后逻辑删除slow结点，返回head。

实现

import java.util.*;

public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        int i = 0;
        for(i = 0; i < n & fast != null; i++) {
            fast = fast.next;
        }
        if(i < n && fast == null) return null;
        while(fast != null) {
            fast = fast.next;
            pre = slow;
            slow = slow.next;
        }
        if(pre == null) {
            return slow.next;
        }
        pre.next = slow.next;
        return head;
    }
}

因为题目保证n有效，比起#链表中倒数最后k个结点#可以删掉一些判断

import java.util.*;

public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        for(int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while(fast != null) {
            fast = fast.next;
            pre = slow;
            slow = slow.next;
        }
        if(pre == null) {
            return slow.next;
        }
        pre.next = slow.next;
        return head;
    }
}