leetcode-19. 删除链表的倒数第 N 个结点

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) {
        // 定义一个哑结点值为 0 并指向 head 节点
        ListNode dummy = new ListNode(0, head);
        // 定义 first 节点并赋值为 head 节点
        ListNode first = head;
        // 定义 second 节点并赋值为 dummy 节点
        ListNode second = dummy;
        // 先让 first 节点比 second 节点先走 n 步
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        // first 节点与 second 节点一起走，直到 first 节点为空
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        // 此时的 second 节点的下一个节点为删除对象，因此让其指向下下个节点
        second.next = second.next.next;
        // 这样就成功删除倒数第 n 个节点
        ListNode ans = dummy.next;
        // dummy.next 指向的是删除后的链表的头节点，并把最终结果赋值给 ans 并返回
        return ans;
    }
}

题解分析

这道题首先考虑用快慢双指针。先定义一个哑结点值为 0 并指向 head 节点，定义 first 节点并赋值为 head 节点，定义 second 节点并赋值为 dummy 节点，先让 first 节点比 second 节点先走 n 步，first 节点与 second 节点一起走，直到 first 节点为空，此时 second 所在位置为要删除节点的前一个节点，因此让其指向下下个节点即可完成删除倒数第 n 个节点的操作。dummy.next 指向的是删除后的链表，并把最终结果赋值给 ans 链表并返回。

leetcode原题： 19. 删除链表的倒数第 N 个结点