day10-删除链表的倒数第 N 个结点

day10-删除链表的倒数第 N 个结点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

day10-删除链表的倒数第 N 个结点

输入: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

解题思路:

快慢指针:让快的指针先移动n位,然后快慢指针一起向后移动,这样的话当快指针移动到链表尾部时,慢指针刚好移动到链表的倒数第n位。

因为我们要删除倒数第n位,那么我们就需要将第n位上一位的next指向第n位的next,所以我们需要知道第n位的前一位(父节点)的位置,所以我们将慢指针设置为快指针移动n+1位后再同时向后移动,这样当快指针移动到链表末尾时,慢指针刚好指向倒数第n位的父节点,这时我们只需要nodeN.next = nodeN.next.next;就可以将第n位删除。

但是对于倒数第n位是链表头的话,它没有父节点,对于这种情况我们做特殊判断,我们只需要返回head.next就可以将头节点删除。

解题代码:

/**
 * 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 nodeN = head;
        ListNode next = head;
        int i=1;
        while(null!=next.next){
            nodeN = i>n ? nodeN.next : nodeN;
            next = next.next;
            ++i;//++i比i++效率更高,i++隐式的生成一个中间变量等于i+1,然后再将隐式变量的值赋值给i。
        }
        if(nodeN==head&&i-1!=n){
            return head.next;
        }else{
            nodeN.next = nodeN.next.next;
        }
        return head;
    }
}

执行效率:

day10-删除链表的倒数第 N 个结点

上一篇:Day10


下一篇:Python面试题_day10