目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
19-删除链表的倒数第N个节点
访问量:1995
一、题目
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
二、解法
思路:双指针p1、p2。p1从head开始往后遍历,p2从第n+1个节点开始往后遍历,当p2到达倒数第一个节点的时候,p1则到达了倒数n+1个节点。
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ // 思路 // 双指针 // head开始遍历 // p2 比 p1 提前n func removeNthFromEnd(head *ListNode, n int) *ListNode { if n== 0 { return head } p1 := head p2 := head for n > 0 { p2 = p2.Next n -- } // 代表删除第一个节点 if p2 == nil { head = head.Next return head } // p1和p2 每次都是往后移动,当p2为null的时候,即p1在倒数第n个节点 for p2.Next != nil { p1 = p1.Next p2 = p2.Next } // 删除倒数第n个节点 p1.Next = p1.Next.Next return head }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助