LeetCode高频题19：删除链表的倒数第 N 个结点

结点"/>

LeetCode高频题19：删除链表的倒数第 N 个结点

LeetCode高频题19：删除链表的倒数第 N 个结点

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

文章目录

• LeetCode高频题19：删除链表的倒数第 N 个结点
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、解题
• 总结

题目

给你一个链表，删除链表的倒数第 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）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题

这也很容易，就是双指针控制我cur指针走到末尾时，我pre指针在倒数第n个节点的前一个节点

啥意思呢？
先让cur走到n步，此时head头结点就是倒数第n个节点了，然后令pre来到头结点的前一个节点，
此后，cur走一步，pre走一步，同步走，两者间隔就是n+1个节点
最后cur走到null时，pre的下一个节点就是倒数第n个要删除的节点。

比如：

（1）最开始pre=null，
（2）cur从head开始走，n=2，n–，cur走，n–，cur走到2，n=0
（3）让n–=-1时，cur再挪一步到3，pre=head，看橘色
（4）然后pre先走，cur再走，粉色
（5）然后pre先走，cur再走，红色
（6）此时cur.next=null时，cur是最后一个节点，pre就是倒数第n=2个节点的前一个节点，pre跳指下下个节点5就完成删除任务

当然，有个特殊情况，如果倒数第n就是head呢？
就是说pre压根一直是null，那直接删除head，返回head.next即可

还有一个情况就是，压根你cur都没有走完n步，说明倒数第n个节点压根不存在，直接返回原来链表
中途呀，咱们统计一下count够不够n个点

懂了这个逻辑，实际上代码就是抠清楚边界

        //复习：//先让cur走到n步，此时head头结点就是倒数第n个节点了，然后令pre来到头结点的前一个节点，//此后，cur走一步，pre走一步，同步走，两者间隔就是n+1个节点//最后cur走到null时，pre的下一个节点就是倒数第n个要删除的节点。public ListNode removeNthFromEndReview(ListNode head, int n) {//让n复用，拿来控制pre和cur的走法，同时让count统计一下是否满了boolean count = false;//用这个来标记好了ListNode cur = head;ListNode pre = null;while (cur != null){n--;//cur必须走//每次走完要统计if (n > 0) count = false;//count标记cur还没有走完n步else if (n == 0) count = true;//此时cur刚刚好走完了n步，还需多走一步else if (n == -1) pre = head;//此时cur多走了一步，pre指向倒数第n前一个else pre = pre.next;//n<-1了，pre和count跟着走就行了cur = cur.next;//先走完n步//不论如何cur都要往下走，所以我统一了}//从while出来，恰好pre就是倒数第n前一个//分析，如果count压根没有走到n，说明节点不够，啥也不删除，返回原链表if (count == false) return head;//够了，但是要删除head的话if (pre == null) return head.next;//pre恰好还没开始指到head//如果pre不是空，就是删除pre.nextpre.next = pre.next.next;//跳指删除return head;}

分两拨测试：
长链

    //造树public static ListNode createList(){ListNode head = new ListNode(1);ListNode n2 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);head.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;return head;}public static void test(){ListNode head = createList();ListNode head2 = createList();Solution solution = new Solution();int n = 2;ListNode res = solution.removeNthFromEnd(head, n);while (res != null){System.out.print(res.val + " ");res = res.next;}System.out.println();res = solution.removeNthFromEndReview(head2, n);while (res != null){System.out.print(res.val + " ");res = res.next;}}public static void main(String[] args) {test();}

测试问题不大

1 2 3 5 
1 2 3 5 

锻炼，恰好删除头结点

//造树public static ListNode createList(){ListNode head = new ListNode(1);ListNode n2 = new ListNode(2);
//        ListNode n3 = new ListNode(3);
//        ListNode n4 = new ListNode(4);
//        ListNode n5 = new ListNode(5);head.next = n2;
//        n2.next = n3;
//        n3.next = n4;
//        n4.next = n5;return head;}

2 
2 

n过长

    //造树public static ListNode createList(){ListNode head = new ListNode(1);ListNode n2 = new ListNode(2);
//        ListNode n3 = new ListNode(3);
//        ListNode n4 = new ListNode(4);
//        ListNode n5 = new ListNode(5);head.next = n2;
//        n2.next = n3;
//        n3.next = n4;
//        n4.next = n5;return head;}public static void test(){ListNode head = createList();ListNode head2 = createList();Solution solution = new Solution();int n = 3;
//         ListNode res = solution.removeNthFromEnd(head, n);
//         while (res != null){
//             System.out.print(res.val + " ");
//             res = res.next;
//         }System.out.println();ListNode res = solution.removeNthFromEndReview(head2, n);while (res != null){System.out.print(res.val + " ");res = res.next;}}public static void main(String[] args) {test();}

返回整个链表

1 2 

LeetCode测试：

这是非常节约时间的做法

你也可以将链表转数组，控制下标搞定
也行

public ListNode removeNthFromEnd(ListNode head, int n) {//一趟，省时间就要花空间List<ListNode> list = new ArrayList<>();ListNode cur = head;int size = 0;while (cur != null){list.add(cur);cur = cur.next;size++;}//统计完成if (size == n) return head.next;//这等价于删除头结点if (size == 1) head = null;//只有一个头结点else list.get(size - n - 1).next = list.get(size - n - 1).next.next;//剩下的删除都是换指针，jvm直接释放return head;}

总结

提示：重要经验：

1）链表操作就是靠操控指针，往往都是双指针操作，要么pre，cur，要么fast，slow，都是这样的，搞清楚边界就行
2）删除普通链表好说，也是找pre和节点和cur，这种该删除倒数第n个，无非就是先让cur走n步，然后pre指向head的前一个节点，就是倒数第n个的前一个节点，跳指删除，中途注意看看是不是删除head，或者n过大，不需要删除
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。