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;
}
}