剑指offer021-删除链表的倒数第n个节点

题目

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：能尝试使用一趟扫描实现吗？

注意：本题与主站 19 题相同： https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

思路

双指针，第一个指针开始遍历，当遍历到n是，第二个指针往后移动

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode lower = new ListNode(0, head);
        ListNode faster = lower;
        while(faster != null){
            if(n < 0){
                lower = lower.next;
            }
            n--;
            faster = faster.next;
        }
        // 删除lower
        if(lower.next == head){
            head = head.next;
        }else{
            lower.next = lower.next.next;
        }

        return head;
    }
}

1
2
3

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:36.4 MB,击败了50.18% 的Java用户

• ← Previous Post
• Next Post →