手撕算法-删除链表的倒数第 N 个结点

描述

思路

快慢指针，快指针先走N步，走不够N步返回空。
慢指针和快指针一起走，当快指针到达终点，即快指针为null时，慢指针到达倒数第N个节点。
因为要删除倒数第N个，所以要记录之前的节点pre，假设倒数第N个节点为cur，删除操作即为：
pre.next = cur.next;
cur.next = null;

因为要返回删除后的头结点，所以假设一个虚拟头结点P，P.next = head;
初始时：pre = P，cur = pre.next;

最后返回P.next；

代码

/**
 * 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 fast = head;
        while(n > 0 && fast != null) {
            fast = fast.next;
            n--;
        }
        if(n != 0){
            return null;
        }

        ListNode p = new ListNode();
        p.next = head;

        ListNode pre = p;
        ListNode cur = p.next;

        while(fast != null) {
            pre = pre.next;
            cur = cur.next;

            fast = fast.next;
        }

        pre.next = cur.next;
        cur.next = null;

        return p.next;
    }
}

面试公司

阿里