数据结构与算法 | Leetcode 19. Remove Nth Node From End of List

栏目: 编程工具 · 发布时间: 5年前

内容简介:原文链接:前面,我们实现了

数据结构与算法 | Leetcode 19. Remove Nth Node From End of List

原文链接: https://wangwei.one/posts/jav...

前面,我们实现了 两个有序链表的合并 操作,本篇来聊聊,如何删除一个链表的倒数第N个节点。

删除单链表倒数第N个节点

Leetcode 19. Remove Nth Node From End of List

给定一个单链表,如: 1->2->3->4->5 ,要求删除倒数第N个节点,假设 N = 2 ,并返回头节点。

则返回结果: 1->2->3->5 .

解法一

这一题的难度标记为 medium ,解法一比较容易想出来,我个人觉得难度不大。

思路

循环两遍:

  1. 先遍历一遍,求得整个链表的长度。
  2. 再遍历一遍,当总长度 len 减去 n ,恰好等于循环的下标 i 时,就找到对应要删除的目标元素,将 prev 节点与 next 节点连接起来即可。

代码

/**
 * 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 null;
        }
        int len = 0;
        for(ListNode curr = head ; curr != null;){
            len++;
            curr = curr.next;
        }
        
        if(len == 0){
            return null;
        }
        
        // remove head
        if(len == n){
            return head.next;
        }
        
        ListNode prev = null;
        int i = 0;
        for(ListNode curr = head; curr != null;){
            i++;
            prev = curr;
            curr = curr.next;
         
            if(i == (len - n)){
                prev.next = curr.next;
            }
        }
        return head;
    }
}

Leetcode测试的运行时间为 6ms ,超过了 98.75%java 代码。

解法二

这种解法,比较巧妙,没有想出来,查了网上的解法,思路如下:

思路

只需要循环一遍,定义两个指针,一个快指针,一个慢指针,让快指针的巧好领先于慢指针 n 步。当快指针到达tail节点时,满指针巧好就是我们需要删除的目标元素。

代码

/**
 * 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 null;
        }
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        
        if(fast == null){
            return slow.next;
        }
        
        ListNode prev = null;
        for(ListNode curr = slow; curr != null; ){
            // when fast arrived at tail, remove slow.
            if(fast == null){
                prev.next =  curr.next;
                break;
            }
            prev = curr;
            curr = curr.next;
            // move fast forward
            fast = fast.next;
        }
        return head;
    }
}

这段代码在LeetCode上的测试结果与解法一的一样。

这种解法与之前的 链表环检测 题目中都使用到了快慢指针,用来定位特定的元素。


以上所述就是小编给大家介绍的《数据结构与算法 | Leetcode 19. Remove Nth Node From End of List》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

文明之光(第四册)

文明之光(第四册)

吴军 / 人民邮电出版社 / 2017-3 / 69.00元

计算机科学家吴军博士继创作《浪潮之巅》、《数学之美》之后,将视角拉回到人类文明史,以他独具的观点从对人类文明产生了重大影响却在过去被忽略的历史故事里,选择了有意思的几十个片段特写,有机地展现了一幅人类文明发展的画卷。《文明之光》系列创作历经整整四年,本书为其第四卷。 作者所选的创作素材来自于十几年来在世界各地的所见所闻,对其内容都有着深刻的体会和认识。《文明之光》系列第四册每个章节依然相对独......一起来看看 《文明之光(第四册)》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码