hazy’s leetcode刷题笔记(一)

为了面试！为了“躺钱”！努力刷题！
一般是发中等难度以上的题目。如果简单难度的题有巧妙的解法也会发一下。（使用的语言是java）

leetcode19. 删除链表的倒数第N个节点 难度：中等
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例： 给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明： 给定的 n 保证是有效的。
进阶： 你能尝试使用一趟扫描实现吗？

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //基本思路：我们只需要记录对于当前节点来说的前面第n+1个节点的引用即可
        //当遍历到最后一个节点时，此时当前节点（即最后一个节点）的前面第n+1个节点的引用自然就是整个链表的倒数第n+1个节点

        //特殊情况判断
        if(head == null) return head;
        if(head.next == null) {
            if(n == 0) return head;
            else return null;
        }
        //倒数第 n + 1个的引用
        ListNode lastN = head;
        //遍历：当前的节点的引用
        ListNode now = head;
        //遍历：当前节点的索引
        int index = 0;

        while(now != null) {
            //当索引大于n时，才将倒数第n + 1个节点的引用进行更新
            if(index > n) lastN = lastN.next;
            //索引和当前节点引用更新
            index++;
            now = now.next;
        }
        //如果去掉第一个节点则直接返回第二个节点
        if(index == n) return head.next;
        //把第n+1个节点的下一个引用变为n-1个节点
        lastN.next = lastN.next.next;

        return head;
    }
}