删除链表的第N个节点，返回头节点Java笔记 - 易塔云建站-模板下载,web开发资源,技术博客

删除链表的第N个节点，返回头节点Java笔记发布于：2021-04-23 17:36:50 来源：力扣查看：45 讨论：0

在某些语言中，由于需要自行对内存进行管理。因此在实际的面试中，对于「是否需要释放被删除节点对应的空间」这一问题，我们需要和面试官进行积极的沟通以达成一致。下面的代码中默认不释放空间。

已知头结点head和第n个节点，求如何找到倒数第n个节点并删除它，返回头结点。
首先最先想到的是，先遍历一遍链表，得到链表的长度，记为length；再次遍历链表，当遍历到位置L -n + 1时，这个节点的下一个节点就是要删除的节点。这个节点是待删除节点的前驱节点。这样再修改一次指针，就完成了删除操作。

为了方便起见，我们将链表的头节点编号为1。
一般操作链表，都设置一个哑结点dummy，防止出现跨越边界的情况。

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode curr = dummy;
        for (int i=1; i<length -n + 1; ++i) {
            curr = curr.next;
        }
        curr.next = curr.next.next;
        return dummy.next;
    }
    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

思路二：链表入栈。先进先出。在要把n节点入栈之前，n节点就是要删除的节点，上一个已经入栈的节点，就是待删除节点的前驱结点。

public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
    Deque<ListNode> stack = new LinkedList<ListNode>();
    ListNode curr = dummy;
    while (curr != null) {
      stack.push(curr);
      curr = curr.next;
}
    for(int i=0; i<n; ++i) {
      stack.pop();//把后来的，大于等于n的节点都弹出去，弹到哪了不知道
    }
    ListNode prev = stack.peek();
    prev.next = prev.next.next;
    return dummy.next;
}

上一篇：Integer.MIN_VALUE和Integer.MAX_VALUE 在Java中的转换下一篇：Redis 与 Map 和 Guava 区别？

评论

最新文章

热门笔记

可以直接扫码关注本站

易塔云建站：15811355317

微信扫一扫，添加好友