文章目录
19. 应用系统定制开发应用系统定制开发删除链表的倒数第 N 个结点:
应用系统定制开发给你一个链表,删除链表的倒数第 n 个结点,应用系统定制开发并且返回链表的头结点。
样例 1:
输入: head = [1,2,3,4,5], n = 2 输出: [1,2,3,5]
- 1
- 2
- 3
- 4
- 5
样例 2:
输入: head = [1], n = 1 输出: []
- 1
- 2
- 3
- 4
- 5
样例 3:
输入: head = [1,2], n = 1 输出: [1]
- 1
- 2
- 3
- 4
- 5
提示:
- 链表中结点的数目为
sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
原题传送门:
分析
- 面对这道算法题目,二当家的陷入了沉思。
- 要删除倒数第N个结点,首先要找到倒数第N+1个结点,然后让这个结点的next指向倒数第N-1个结点。
- 要找到倒数第N+1个结点,首先考虑要取得链表的长度,然后就知道这个结点的正数位置,这样需要遍历两次链表。
- 还可以使用动态数组,也就是list,一边遍历链表,一边把结点的引用或者指针放入,这样就可以在知道总数之后,直接按照下标取得目标结点,时间复杂度降低了,但是却是以空间为代价。
- 事实上,我们可以只用常数空间的代价换来时间复杂度的降低,倒数第N+1个结点就是距离最后一个结点N个位置的结点,可以用双指针,先让快指针遍历N个结点,之后快慢指针同时遍历链表,等到快指针指向空,慢指针刚好指向我们要的结果。要注意的一点是,因为有可能最终要删除的结点是头结点,为了让算法能统一处理所有情况,需要在头结点前面加入一个哑结点,让慢指针指向这个哑结点,也就是头结点的前一个结点,这样链表中的每个结点就都有了前结点。
题解
rust
// 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 { pub fn remove_nth_from_end(head: Option<Box<ListNode>>, mut n: i32) -> Option<Box<ListNode>> { let mut dummy = Some(Box::new(ListNode::new(-1))); dummy.as_mut().unwrap().next = head; let mut slow = &mut dummy; let mut fast = &slow.clone(); while n >= 0 { if let Some(n) = fast { fast = &n.next; } else { return None; } n -= 1; } while fast.is_some() { slow = &mut slow.as_mut().unwrap().next; fast = &fast.as_ref().unwrap().next; } slow.as_mut().unwrap().next = slow.as_mut().unwrap().next.as_mut().unwrap().next.take(); return dummy.unwrap().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
- 36
- 37
- 38
- 39
- 40
- 41
go
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{0, head} fast, slow := head, dummy for i := 0; i < n; i++ { fast = fast.Next } for ; fast != nil; fast = fast.Next { slow = slow.Next } slow.Next = slow.Next.Next return dummy.Next}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
c++
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy = ListNode(0, head); ListNode *fast = head; ListNode *slow = &dummy; for (int i = 0; i < n; ++i) { fast = fast->next; } while (fast) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; return dummy.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
python
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) fast = head slow = dummy for i in range(n): fast = fast.next while fast: fast = fast.next slow = slow.next slow.next = slow.next.next return dummy.next
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
java
/** * 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, head); ListNode fast = head; ListNode slow = dummy; for (int i = 0; i < n; ++i) { fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummy.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
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 博客原创~