Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
思路:
假设我们想要删除倒数第1个节点5,那么我们应该把指针停留在倒数第2个节点4处,因为我们要进行node.next = node.next.next的节点删除操作。由此可见,如果我们想要删除倒数第n个节点的话,我们应该把指针停留在倒数n+1个节点处。
我们需要两个指针,一个先走,一个后走。等前面走了n+1步之后,后面的指针再走,此时两个指针保持恒定的距离n+1一直行走,直到前面的指针达到链表尾部。而此时后面跟着的指针到链表尾部的距离为n+1,也就是处在倒数第n+1个节点处,它的next节点就是要删除的倒数第n个节点,接下来就可以进行节点删除操作。
注意:
- 一定要创建一个dummy节点让其next为head,因为有可能链表只有一个元素,删除之后就为空,处理起来就麻烦了。
- 当链表有环的时候,下面的程序不适用,因为会出现死循环。
public ListNode removeNthFromEnd(ListNode head, int n) { if(head==null) return null; ListNode dummy = new ListNode(0); dummy.next = head; ListNode h = dummy; while(head != null) { head = head.next; if(n < 0 || --n < 0) { // n<0的话就不用再自减了,防止整数溢出 h = h.next; } } h.next = h.next.next; return dummy.next; }
上面的代码还是不太好理解,下面的更好理解:
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode node = dummy; while(n-->0) head = head.next; while(head != null) { head = head.next; node = node.next; } node.next = node.next.next; return dummy.next; }
再补充个C++的代码:
ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *node=head, **cur = &head; while(n--) node = node->next; while(node) { node = node->next; cur = &(*cur)->next; } *cur = (*cur)->next; return head; }
相关推荐
19.Remove_Nth_Node_From_End_of_List删除链表的倒数第N个节点【LeetCode单题讲解系列】
扔鸡蛋 leetcode LeetCode-Note-Mary Mary's ...List(删除链表的倒数第N个节点) 153. Find Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值) 2020/12/09 300. Longest Increasing
19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove ...
leetcode 2 Leetcode答案集 关于项目: 本项目包含本人LeetCode解题的答案,全部将由JavaScript语言进行解答。并会在每个题目的文件夹中添加相关的思路解析。 详情 # Title Solution Time Space Difficulty 1 Two ...
leetcode 316 leetcode 题解更新脚本 用于快速的更新题解、同步leetcode的做题情况。 题解见: 文件名 用途 add_to_blog_solution_table.py 添加题解地址or题解语言到表格,能同步leetcode新题情况 blog_solution_...
Remove Nth Node From End of List LeetCode 42 Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode ...
leetcode括号生成python leetcode 打算开始在leetcode上刷题了嗯。 希望不要因为各种各样的原因半途而废…… 2015.3.28 在这里贴一下写过的题解和思路。 长期更新。 #19 Remove Nth Node From End of List Given a ...
Remove Nth Node From End of List Swap Nodes in Pairs Spiral Matrix Path Sum II Copy List with Random Pointer Building H2O Fizz Buzz Multithreaded hard Merge k Sorted Lists Reverse Nodes in k-Group ...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
leetcode 跳跃 leetcode 数据结构和算法是一个程序员的基石,本仓库用于个人学习基本数据结构和算法。 序号 题目名称 难易程度 归类 备注 1 两数之和 数组 2 两数相加 中等 链表 3 无重复字符的最长子串 7 整数反转 ...
26 | [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)| [C++](./C++/remove-duplicates-from-sorted-array.cpp) [Python](./Python/remove-duplicates...
2sum leetcode ...Remove_Nth_Node_From_End_of_List.cpp - invert_Binary_Tree.cpp - 对称树.cpp - BST_Or_Not.cpp - level_order_traversal.cpp - exponentiation_by_squaring.cpp - Maximum_Depth_B
java二叉树算法源码 ...Remove Nth Node From End of List Medium 21 合并两个有序链表 Merge Two Sorted Lists Easy 141 判断链表是是否存在环 Linked List Cycle Easy 142 环形链表II Linked List Cycle I
19.Remove Nth Node From End of List: 本题要求移除倒数第n个点,进阶解法要求只遍历一遍完成。 我采用字典,将节点编号和节点存进字典里,这样遍历一遍记得到了所有,然后移除即可。 看了答案的一遍过滤的方法是用...
lru cache leetcode #算法解题报告 主要记录我每天做的题目,包括leetcode, 剑指offer等在线编程平台,以前做过的等时间够再一起...19.Remove Nth Node From End of List 20.Valid Parentheses 21.Merge Two Sorted L
leetcode添加元素使和等于 programmer_practices algorithm practices 最优解Book: 双栈实现getMin Stack. 双栈实现Queue. 递归和栈实现逆序操作一个栈. 仅用一个栈排序另一个栈. 打印两个有序链表的公共部分. 删除...
lru缓存leetcode leetcode 我的 leetcode Javascript / Swift / Mysql 解决方案 典型问题 动态规划 子阵列 ..../topics/linked-list/remove-nth-node-from-end-of-list.md) 规则 常见的 分而治之 常见的
题目来源:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 题目 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了...
leetcode 面试清单 Java 比较器与比较器 哈希 静止的 例外 线 泛型 算法 链表 Linked List Cycle Remove Nth Node From End of List Merge Two Sorted Lists 两个链表的交集 Remove Duplicates from Sorted List ...
Remove Nth Node From End of List Swap Nodes in Pairs Reverse Nodes in k-Group Copy List with Random Pointer Linked List Cycle Linked List Cycle II Reorder List LRU Cache Palindrome Linked List 字符串 ...