LeetCode 19. Remove Nth Node From End of List [Medium]

发表于 更新于 分类于 ， 阅读次数：

LeetCode 19.

题目来源：https://leetcode.com/problems/remove-nth-node-from-end-of-list

题目难度：Medium

链表定义

1
2
3
4
5
6
7
8
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

解法1[Java]：

核心思想

遍历两次，第一次算出链表长度，第二次，定位到要删除的节点的前一个节点。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int length = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }
        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }
}

解法2[Java]：双指针

核心思想

  • 核心目的：我们要定位到要删除元素的前一个元素。

当链表长度为 len 时，

  • 如果我们要删除倒数第1个节点，也就是要删除第len-0个节点，那么我们就要定位到第 len-1 个节点。
  • 如果我们要删除倒数第2个节点，也就是要删除第len-1个节点，那么我们就要定位到第 len-2 个节点。
  • 如果我们要删除倒数第n个节点，也就是要删除第 len-(n-1) 个节点，即第 len-n+1个节点。那么我们就要定位到第 len-n 个节点。

1号指针指向头节点之前的辅助节点，相当于第0个节点。2号指针最初也指向“第0节点”，然后2号指针遍历n+1次，到达第n+1个节点。此时，两个指针之间的差距为 n+1，两个指针同时向右移动，当2号指针变为null的时候，相当于指向了第len+1个节点的时候，1号指针应该指向第 (len+1)-(n+1) 个节点，也就是第 len-n 个节点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        // Advances first pointer so that the gap between first and second is n nodes
        // apart
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        // Move first to the end, maintaining the gap
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}