No.019：Remove Nth Node From End of List-白红宇的个人博客

No.019：Remove Nth Node From End of List

发布日期：2021-05-09 03:58:59 浏览次数：14 分类：博客文章

本文共 2165 字，大约阅读时间需要 7 分钟。

问题：

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

官方难度：

Easy

翻译：

给定一个链表，删除其中倒数第n个节点，方法返回头节点。

例子：

链表: 1->2->3->4->5，n=2。

删除节点后的链表：1->2->3->5。

本题的节点定义，同No.002（Add Two Numbers）相同。

首先需要确定，给定链表的长度，之后定位待删除的节点，和此节点的前一个节点。由于是原生态的链表，没有现成的定位方法，所以为了提高效率，在确定链表长度的同时，将节点放入容器中，以便之后获取节点。

需要考虑删除第一个节点的特殊情况，此时没有上一个节点。

将失去引用的节点，即删除的节点置null，防止可能的内存泄漏。

最后剩下一个问题，使用什么容器合适？HashMap和ArrayList在性能上要比LinkedList要高，HashMap空间占用更大，所以应该是用ArrayList比较好。不过ArrayList是基于数组实现的，所以我也尝试着使用一个长度不断扩张的数组来实现。

最后入参检查，对n的检查放在确定链表长度之后。

解题代码：

1     public static ListNode removeNthFromEnd(ListNode head, int n) { 2         if (head == null) { 3             throw new IllegalArgumentException("Input error"); 4         } 5         ListNode current = head; 6         ListNode[] array = new ListNode[] {}; 7         int length = 1; 8         while (current != null) { 9             array = extendArray(array, current);10             current = current.next;11             length++;12         }13         if (n > length) {14             throw new IllegalArgumentException("Input error");15         }16         // 记录删除节点，以及上一个节点17         int index = length - n;18         int lastIndex = length - n - 1;19         // 删除第一个节点的情况20         if (lastIndex == 0) {21             head = head.next;22         } else {23             ListNode deleteNode = array[index - 1];24             ListNode lastNode = array[lastIndex - 1];25             lastNode.next = deleteNode.next;26             deleteNode = null;27         }28         return head;29     }30 31     private static ListNode[] extendArray(ListNode[] array, ListNode node) {32         ListNode[] listArray = new ListNode[array.length + 1];33         System.arraycopy(array, 0, listArray, 0, array.length);34         listArray[array.length] = node;35         return listArray;36     }37 38     private static class ListNode {39         int val;40         ListNode next;41 42         ListNode(int x) {43             val = x;44         }45     }

removeNthFromEnd

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章