原创

19-删除链表的倒数第N个结点

温馨提示:
本文最后更新于 2021年08月06日,已超过 487 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

描述

难度:中等

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

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

示例 1:

img

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1
输出:[]
示例 3:

输入:head = [1,2], n = 1
输出:[1]

提示:

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

假如有链表:

img

n=2,即删除倒数第2个节点,也就是这里的第 5-2 = 3 个节点(从0开始遍历)

假如 n=5,即要删除第一个节点,那要如何判断呢?

常用的技巧是添加一个哑节点(dummy node),它的 next 指针指向链表的头节点。

变成: 0—>1—>2—>3—>4—>5—>null

  • 第一种解法:通过长度遍历

删除倒数第N个节点,也就是删除第 length-N 个节点。

所以第一步我们要获取这个链表的长度

我们知道要删除第3个节点 ,接下来就是找到第3个节点的前一个节点,指向当前节点的下一个节点。

第二步就是遍历这个链表,找到它的删除节点的上一个节点

  • 第二种解法:辅助栈

利用 栈 找到目标删除节点,这种方法容易理解,见代码。

  • 第三种解法:双指针

双指针简单一点,first 指针指向cur.next(在右),second 指向 cur(在左),如何让first 先走 n 步(n是要删除的倒数节点,假设 n=2),然后first、second 一起走到first的尾部。

1、第一步

S 在原点,F 在下一位

S  F
|  |
0—>1—>2—>3—>4—>5—>null

2、第二步

F向前走n步

S         F            
|         |            
0—>1—>2—>3—>4—>5—>null

3、第三步

判断标准为F不为空前,S、F一起走

          S             F
          |           |
0—>1—>2—>3—>4—>5—>null

S.next = S.next.next 即可

解法

public class 删除链表的倒数第N个结点19 {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(3);
        listNode.next.next.next = new ListNode(4);
        listNode.next.next.next.next = new ListNode(5);

        ListNode resultListNode = removeNthFromEnd2(listNode, 5);
        printListNode(resultListNode);
    }



    /**
     *
     * 解法一,先求长度
     * 一种常用的技巧是添加一个哑节点(dummy node),它的next 指针指向链表的头节点。
     * 这样一来,我们就不需要对头节点进行特殊的判断了。
     *
     *
     * 复杂度分析
     * 时间复杂度:O(L),其中 L 是链表的长度。
     * 空间复杂度:O(1)。
     *
     * @param head
     * @param n
     * @return
     */
    static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        //此节点前的都是正常遍历,
        //length-n+1 即删除节点前一个
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;
    }
    static int getLength(ListNode listNode) {
        int i = 0;
        while (listNode != null) {
            i++;
            listNode = listNode.next;
        }
        return i;
    }

    /**
     * 解法二:栈
     *
     * 复杂度分析
     * 时间复杂度:O(L),其中 L 是链表的长度。
     * 空间复杂度:O(L),其中 L 是链表的长度。主要为栈的开销
     *
     */
    static ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //从后往前,弹出n个栈
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        //prev是要删除的目标节点的上一个节点
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return dummy.next;
    }

    /**
     *
     * 解法三,双指针
     *
     * 复杂度分析
     * 时间复杂度:O(L),其中 L 是链表的长度。
     * 空间复杂度:O(1)
     *
     */
    static ListNode removeNthFromEnd4(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = dummy.next;
        ListNode second = dummy;
        //让first先跑n步
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    /**
     * 打印链表
     *
     * @param head
     */
    static void printListNode(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}
正文到此结束
关注公众号 【HelloCoder】
免费领取Java学习资料
让技术,化繁为简
本文目录