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

2019-07-17  本文已影响0人  杨柳滔滔

题目

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

示例:

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

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

说明:

给定的 n 保证是有效的。

进阶:

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

头节点的应用

(引用百度百科)
讲到链表不得不讲到头节点,数据结构中,在单链表的第一个结点之前附设一个结点,它没有直接前驱,称之为头结点
头结点是链表里面第一个结点,他的数据域可以不存放任何信息(有时候也会存放链表的长度等等信息),他的指针区域存放的是链表中第一个数据元素的结点(就是传说中的首元结点)存放的地址。

思路

图解

用ppt做的gif


图解算法.gif

代码

public class removeNthFromEnd {
    public ListNode removeNthFromEndSolution(ListNode head, int n) {

        ListNode preNode = new ListNode(0);
        preNode.next = head;
        ListNode fastNode = preNode, slowNode = preNode;

        while (n > 0) {
            fastNode = fastNode.next;// 采用快慢节点
            n--;
        }
        while (fastNode.next != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;// 快慢节点距离始终一致,等快节点到终点的时候,慢节点刚好落在了需要删除的那个节点上面
        }
        slowNode.next = slowNode.next.next;// 删除节点
        return preNode.next;
    }
}

上一篇下一篇

猜你喜欢

热点阅读