寒光博客

[LeetCode]19. 删除链表的倒数第N个节点
题目 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2-...
扫描右侧二维码阅读全文
24
2020/06

[LeetCode]19. 删除链表的倒数第N个节点

题目

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

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

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

链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

分析及反思

双指针 第一个指针先移动n次,随后第二个指针和第一个指针同步后移 直到第一个的next为null的时候 第二个指针的下一个就是倒数第n个 还是很妙的 这种解法。一次遍历即可完成。

然后就是问题实践解决中,我直接从head开始遍历 没有设置头结点,导致在{[1],1}这个测试点的时候无法删除第一个节点报错的问题。
所以类似的节点问题一定要添加头结点,,是最稳的解法。

代码

//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode(int x) {
//        val = x;
//    }
//}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;//头节点
        ListNode start = pre, end = pre;
        while (n-- != 0) {
            start = start.next;
        }
        while (start.next != null) {
            start = start.next;
            end = end.next;
        }
        end.next = end.next.next;
        return pre.next;
//        ListNode p, q;
//        p = q = head;
//        int count = 0;
//        while (q.next != null) {
//            if (count != n) {
//                q = q.next;
//                count++;
//            } else {
//                q = q.next;
//                p = p.next;
//            }
//        }
//        p.next = p.next.next;
//        return head;
    }
}
本文作者:Author:     文章标题:[LeetCode]19. 删除链表的倒数第N个节点
本文地址:https://dxoca.cn/Algorithm/368.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:June 24th, 2020 at 01:41 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment