美文网首页Leetcode模拟面试算法提高之LeetCode刷题Leetcode
LeetCode-19 删除链表中的倒数第N个节点

LeetCode-19 删除链表中的倒数第N个节点

作者: 编程半岛 | 来源:发表于2019-06-02 18:20 被阅读2次
    • 题目:19. 删除链表中的倒数第N个节点
    • 难度:中等
    • 分类:链表
    • 解决方案:双指针

    今天我们学习第19题删除链表中的倒数第N个节点,这是一道中等题。这个题属于面试中的高频题,一定要能手写出来。下面我们看看这道题的题目描述。

    题目描述

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

    示例:
    给定一个链表: 1->2->3->4->5, 和 n = 2.
    当删除了倒数第二个节点后,链表变为 1->2->3->5.
    

    说明:给定的n保证是有效的。

    进阶:你能尝试使用一趟扫描实现吗?

    分析

    这个题是目前为止遇到的第一个链表题,对于链表不太熟悉的小伙伴可以扫描文章下方的二维码,关注『 算法半岛』回复『 数据结构目录』,即可获得相关学习资料。

    这个题让我们删除链表中的倒数第n个节点,并且返回头节点。题目中说明部分提到给定的n保证是有效的,因此n的值小于等于链表的长度。最基本的方法,我们可以先遍历一次链表,统计链表的长度len,则删除的节点位置为len-n+1。然后找到删除节点位置的前一个节点(位置为len-n)对节点进行删除即可。注意如果删除的节点为第一个节点,则直接返回head.next即可。对示例分析如下图所示:

    两次遍历方法

    上述分析所对应的java代码如下所示:

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            
            if(head == null){
                return head;
            }
            
            ListNode p = head;
            int len = 1;
            
            // 统计链表节点的个数
            while(p.next != null){
                p = p.next;
                len++;
            }
            
            // 计算删除节点的位置
            int pos = len - n + 1;
            
            // 删除节点如果为第一个节点,则直接返回head.next
            if(pos == 1)
                return head.next;
            
            // 重置p指针的位置
            p = head;
            
            // 查找需要删除节点的前一个节点
            for(int i=1; i<pos-1; i++){
                p = p.next;
            }
            
            // 删除该节点
            p.next = p.next.next;
            
            return head;
        }
    }
    
    两次遍历提交结果

    进阶部分提示我们尝试使用一趟扫描实现,对于这样的题,我们可以使用双指针(快慢指针)来实现。具体分析过程如下图所示:

    快慢指针法

    值得注意的是,当删除的结点为第一个节点,则fast==null,因此在fastn步后需要判断fast是否为null,如果为null则直接返回fast.next

    上述分析所对应的java代码如下所示:

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
           
            // 声明快慢指针
            ListNode fast = head, slow = head;
            
            // fast指针走n步
            while(n > 0){          
                fast = fast.next;
                n--;
            }
            
            // 判断需要删除的节点是否为第一个节点
            if(fast == null){
                return head.next;
            }
            
            // 同时移动快慢指针
            while(fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
            
            // 删除节点
            slow.next = slow.next.next;
            
            return head;
        }
    }
    
    快慢指针提交结果

    Github地址

    LeetCode-19 删除链表中的倒数第N个节点

    参考链接

    删除链表中的倒数第N个节点

    更多文章,请扫描二维码关注『算法半岛』

    相关文章

      网友评论

        本文标题:LeetCode-19 删除链表中的倒数第N个节点

        本文链接:https://www.haomeiwen.com/subject/hmzxxctx.html