本文共 1362 字,大约阅读时间需要 4 分钟。
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]示例 2:
输入:head = [1], n = 1
输出:[]示例 3:
输入:head = [1,2], n = 1
输出:[1]
提示:
链表中结点的数目为 sz
1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
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) { if (head == null) { return null; } ListNode temp = new ListNode(0, head); ListNode slow = temp; ListNode fast = head; while (n>0) { //这里是防止n大于链表深度,题意已假设不存在,可省略 if (fast==null) { return null; } fast = fast.next; --n; } while (fast!=null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return temp.next; }}
- 快慢指针,快指针先走n步,然后快慢指针同步走,直到快指针到达尾部,此时慢指针正好走到倒数第n个节点,但是此时删除该节点不好处理,好的时机是走到该节点前一个节点,方便删除,所以我们为慢指针在头部插入一个虚节点,让慢指针从这里往下走;
- 注意记录慢指针头部,且最后要注意返回假头部节点的next;