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

Category	Difficulty	Likes	Dislikes
algorithms	Medium (45.32%)	2477	-

Tags

linked-list | two-pointers

Companies

Unknown

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

Discussion | Solution

解法

 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
36
37
38
39
40
41
42
43
// @lc code=start
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    /// ## 解题思路
    /// - 双指针 + dummy node
    /// 1. 在原表头前面增加一个dummy, 以统一处理原head结点需要处理的情况;
    /// 2. 设置2个指针, 一前一后遍历链表, 前指针提前n个节点;
    /// 3. 然后将前后指针同时遍历,直到前指针到达尾节点;
    /// 4. 将前指针next指向其next->next;
    pub fn remove_nth_from_end(mut head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        // 设置dummy节点
        let mut dummy = Box::new(ListNode::new(0));
        dummy.next = head;
        let mut pre_p = dummy.clone(); //
        for _ in 0..(n as usize) {
            pre_p = pre_p.next.unwrap();
        }
        let mut p = dummy.as_mut();
        while pre_p.next.is_some() {
            pre_p = pre_p.next.unwrap();
            p = p.next.as_mut().unwrap();
        }
        p.next = p.next.as_mut().unwrap().next.take();

        dummy.next
    }
}
// @lc code=end

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

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

解法

相关文章：