首页 > 其他 > 详细

LeetCode19. 删除链表的倒数第 N 个结点

时间:2021-05-12 09:58:14      阅读:18      评论:0      收藏:0      [点我收藏+]

LeetCode19. 删除链表的倒数第 N 个结点

题目描述

/**
     * 
     * 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
     * <p>
     * 进阶:你能尝试使用一趟扫描实现吗?
     * 
     */

思路分析

  1. 要删除链表的倒数第n个节点,可以考虑先计算链表的总长度
  2. 然后用链表的 总长度 - n,则为顺数的要删除的节点
  3. 因为链表的头节点不能动,头节点改变后,链表会发生改变,所以定义辅助指针cur指向链表的头节点,进行移动
  4. 因为是单链表,所以如果直接找到要删除的节点,则删除不掉,因此需要找到要删除节点的前一个节点
  5. 然后让前一个节点cur : 执行 cur.next = cur.next.next,即可完成该节点的删除
  6. 考虑要删除的节点是第一个和倒数第一个的特殊情况
  7. 详见源码分析

源码及分析

//思路分析
    //1. 计算来链表的长度,用链表的长度-倒数第n个节点,就是顺序删除的节点
    //2. 单向链表删除节点需要找到这个节点的前一个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //数据jiaoyan
        if (head == null) {
            return null;
        }
        //定义辅助指针指向链表的第一个节点,因为头指针不能动
        ListNode cur = head;
        //定义变量保存链表的长度
        int count = 0;
        //当循环结束时,链表的长度即为count
        while (true) {
            if (cur == null) {
                break;
            }
            count++;
            cur = cur.next;
        }
        // 链表长度为 count,要删除倒数第n个,即顺数的count - n个
        int order = count - n;
        //判断是否要删除第一个节点
        if (order == 0){
            head = head.next;
        }
        //再遍历链表找到要删除节点的前一个节点
        cur = head;
        for (int i = 1; i < order - 1; i++) {
            cur = cur.next;
        }
        //循环结束时 cur指向要删除节点的前一个节点

        //判断是不是要删除最后一个节点
        if (n != 1) {
            cur.next = cur.next.next;
        }else {
            cur.next = null;
        }
        //返回头节点
        return head;
    }

LeetCode19. 删除链表的倒数第 N 个结点

原文:https://www.cnblogs.com/mx-info/p/14758288.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!