LeetCode 19.
题目来源:https://leetcode.com/problems/remove-nth-node-from-end-of-list
题目难度:Medium
链表定义
1 | /** |
解法1[Java]:
核心思想
遍历两次,第一次算出链表长度,第二次,定位到要删除的节点的前一个节点。
算法
1 | class Solution { |
解法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 | class Solution { |