删除链表的倒数第N个节点

发表于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，19. Remove Nth Node From End of LIst

先看题目描述

大意就是给定一个链表，再给定一个数字 n，让我们删除链表中的倒数第 n 个节点

算法和思路

如果是遍历两遍的话，代码很容易实现，先遍历一遍统计链表长度 len，再遍历一遍来删除正数第 len - n + 1 个节点

但题目要求只遍历一遍，那么就使用双指针法

双指针法

算法流程：

  • 定义两个指针 p 和 q 指向链表的头节点 head
  • 将 q 指针向后移动 n 位
  • 同时向右移动 p 指针和 q 指针直至 q 指针为空，移动过程中用 pre 指针来指向 p 指针的前置节点
  • 当 q 指针为空时，p 指针指向的节点就是要删除的节点
  • 删除掉 p 指针指向节点并返回链表即可

注意：为了解决删除头节点的问题，可以定义一个哑节点 dumpy，令其 next 为 head 节点，初始化 pre 指针时使其指向 dumpy 节点，最终结果返回 dumpy.next

算法源码

两次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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) {
        int len = 0;
        ListNode node = head;
        while (node != null) {
            len++;
            node = node.next;
        }
        if (n == len) {
            ListNode ans = head.next;
            head.next = null;
            return ans;
        }
        int con =  len - n + 1;
        node = head;
        ListNode pre = null;
        for (int i = 1; i < con; i++) {
            pre = node;
            node = node.next;
        }
        pre.next = node.next;
        node.next = null;
        return head;
    }
}

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode q = head;
        ListNode p = head;
        ListNode pre = dummy;
        for (int i = 0; i < n; i++) {
            q = q.next;
        }
        while (q != null) {
            pre = p;
            p = p.next;
            q = q.next;
        }
        pre.next = p.next;
        p.next = null;
        return dummy.next;
    }
}