首页 > 专栏 > 数据结构与算法 > 文章详情
删除链表的第N个节点,返回头节点Java笔记 发布于:2021-04-23 17:36:50   来源:力扣   查看:45  讨论:0
在某些语言中,由于需要自行对内存进行管理。因此在实际的面试中,对于「是否需要释放被删除节点对应的空间」这一问题,我们需要和面试官进行积极的沟通以达成一致。下面的代码中默认不释放空间。dmk易塔云建站-模板下载,web开发资源,技术博客
dmk易塔云建站-模板下载,web开发资源,技术博客
已知头结点head和第n个节点,求如何找到倒数第n个节点并删除它,返回头结点。dmk易塔云建站-模板下载,web开发资源,技术博客
首先最先想到的是,先遍历一遍链表,得到链表的长度,记为length;再次遍历链表,当遍历到位置L -n + 1时,这个节点的下一个节点就是要删除的节点。这个节点是待删除节点的前驱节点。这样再修改一次指针,就完成了删除操作。

为了方便起见,我们将链表的头节点编号为1。dmk易塔云建站-模板下载,web开发资源,技术博客
一般操作链表,都设置一个哑结点dummy,防止出现跨越边界的情况。
dmk易塔云建站-模板下载,web开发资源,技术博客

/**dmk易塔云建站-模板下载,web开发资源,技术博客
 * Definition for singly-linked list.dmk易塔云建站-模板下载,web开发资源,技术博客
 * public class ListNode {dmk易塔云建站-模板下载,web开发资源,技术博客
 *     int val;dmk易塔云建站-模板下载,web开发资源,技术博客
 *     ListNode next;dmk易塔云建站-模板下载,web开发资源,技术博客
 *     ListNode() {}dmk易塔云建站-模板下载,web开发资源,技术博客
 *     ListNode(int val) { this.val = val; }dmk易塔云建站-模板下载,web开发资源,技术博客
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }dmk易塔云建站-模板下载,web开发资源,技术博客
 * }dmk易塔云建站-模板下载,web开发资源,技术博客
 */dmk易塔云建站-模板下载,web开发资源,技术博客
 class Solution {dmk易塔云建站-模板下载,web开发资源,技术博客
    public ListNode removeNthFromEnd(ListNode head, int n) {dmk易塔云建站-模板下载,web开发资源,技术博客
        ListNode dummy = new ListNode(0, head);dmk易塔云建站-模板下载,web开发资源,技术博客
        int length = getLength(head);dmk易塔云建站-模板下载,web开发资源,技术博客
        ListNode curr = dummy;dmk易塔云建站-模板下载,web开发资源,技术博客
        for (int i=1; i<length -n + 1; ++i) {dmk易塔云建站-模板下载,web开发资源,技术博客
            curr = curr.next;dmk易塔云建站-模板下载,web开发资源,技术博客
        }dmk易塔云建站-模板下载,web开发资源,技术博客
        curr.next = curr.next.next;dmk易塔云建站-模板下载,web开发资源,技术博客
        return dummy.next;dmk易塔云建站-模板下载,web开发资源,技术博客
    }dmk易塔云建站-模板下载,web开发资源,技术博客
    public int getLength(ListNode head) {dmk易塔云建站-模板下载,web开发资源,技术博客
        int length = 0;dmk易塔云建站-模板下载,web开发资源,技术博客
        while (head != null) {dmk易塔云建站-模板下载,web开发资源,技术博客
            ++length;dmk易塔云建站-模板下载,web开发资源,技术博客
            head = head.next;dmk易塔云建站-模板下载,web开发资源,技术博客
        }dmk易塔云建站-模板下载,web开发资源,技术博客
        return length;dmk易塔云建站-模板下载,web开发资源,技术博客
    }dmk易塔云建站-模板下载,web开发资源,技术博客
}
思路二:链表入栈。先进先出。在要把n节点入栈之前,n节点就是要删除的节点,上一个已经入栈的节点,就是待删除节点的前驱结点。
public ListNode removeNthFromEnd(ListNode head, int n) {dmk易塔云建站-模板下载,web开发资源,技术博客
    ListNode dummy = new ListNode(0, head);dmk易塔云建站-模板下载,web开发资源,技术博客
    Deque<ListNode> stack = new LinkedList<ListNode>();dmk易塔云建站-模板下载,web开发资源,技术博客
    ListNode curr = dummy;dmk易塔云建站-模板下载,web开发资源,技术博客
    while (curr != null) {dmk易塔云建站-模板下载,web开发资源,技术博客
        stack.push(curr);dmk易塔云建站-模板下载,web开发资源,技术博客
        curr = curr.next;dmk易塔云建站-模板下载,web开发资源,技术博客
    }dmk易塔云建站-模板下载,web开发资源,技术博客
    for(int i=0; i<n; ++i) {dmk易塔云建站-模板下载,web开发资源,技术博客
        stack.pop();//把后来的,大于等于n的节点都弹出去,弹到哪了不知道dmk易塔云建站-模板下载,web开发资源,技术博客
    }dmk易塔云建站-模板下载,web开发资源,技术博客
    ListNode prev = stack.peek();dmk易塔云建站-模板下载,web开发资源,技术博客
    prev.next = prev.next.next;dmk易塔云建站-模板下载,web开发资源,技术博客
    return dummy.next;dmk易塔云建站-模板下载,web开发资源,技术博客
}

评论

  • 匿名