在某些语言中,由于需要自行对内存进行管理。因此在实际的面试中,对于「是否需要释放被删除节点对应的空间」这一问题,我们需要和面试官进行积极的沟通以达成一致。下面的代码中默认不释放空间。
NtM易塔云建站-模板下载,web开发资源,技术博客NtM易塔云建站-模板下载,web开发资源,技术博客已知头结点head和第n个节点,求如何找到
倒数第n个节点并删除它,返回头结点。
NtM易塔云建站-模板下载,web开发资源,技术博客首先最先想到的是,先遍历一遍链表,得到链表的长度,记为length;再次遍历链表,当遍历到位置L -n + 1时,这个节点的下一个节点就是要删除的节点。这个节点是待删除节点的前驱节点。这样再修改一次指针,就完成了删除操作。
为了方便起见,我们将链表的头节点编号为1。NtM易塔云建站-模板下载,web开发资源,技术博客
一般操作链表,都设置一个哑结点dummy,防止出现跨越边界的情况。NtM易塔云建站-模板下载,web开发资源,技术博客
/**NtM易塔云建站-模板下载,web开发资源,技术博客
* Definition for singly-linked list.NtM易塔云建站-模板下载,web开发资源,技术博客
* public class ListNode {NtM易塔云建站-模板下载,web开发资源,技术博客
* int val;NtM易塔云建站-模板下载,web开发资源,技术博客
* ListNode next;NtM易塔云建站-模板下载,web开发资源,技术博客
* ListNode() {}NtM易塔云建站-模板下载,web开发资源,技术博客
* ListNode(int val) { this.val = val; }NtM易塔云建站-模板下载,web开发资源,技术博客
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }NtM易塔云建站-模板下载,web开发资源,技术博客
* }NtM易塔云建站-模板下载,web开发资源,技术博客
*/NtM易塔云建站-模板下载,web开发资源,技术博客
class Solution {NtM易塔云建站-模板下载,web开发资源,技术博客
public ListNode removeNthFromEnd(ListNode head, int n) {NtM易塔云建站-模板下载,web开发资源,技术博客
ListNode dummy = new ListNode(0, head);NtM易塔云建站-模板下载,web开发资源,技术博客
int length = getLength(head);NtM易塔云建站-模板下载,web开发资源,技术博客
ListNode curr = dummy;NtM易塔云建站-模板下载,web开发资源,技术博客
for (int i=1; i<length -n + 1; ++i) {NtM易塔云建站-模板下载,web开发资源,技术博客
curr = curr.next;NtM易塔云建站-模板下载,web开发资源,技术博客
}NtM易塔云建站-模板下载,web开发资源,技术博客
curr.next = curr.next.next;NtM易塔云建站-模板下载,web开发资源,技术博客
return dummy.next;NtM易塔云建站-模板下载,web开发资源,技术博客
}NtM易塔云建站-模板下载,web开发资源,技术博客
public int getLength(ListNode head) {NtM易塔云建站-模板下载,web开发资源,技术博客
int length = 0;NtM易塔云建站-模板下载,web开发资源,技术博客
while (head != null) {NtM易塔云建站-模板下载,web开发资源,技术博客
++length;NtM易塔云建站-模板下载,web开发资源,技术博客
head = head.next;NtM易塔云建站-模板下载,web开发资源,技术博客
}NtM易塔云建站-模板下载,web开发资源,技术博客
return length;NtM易塔云建站-模板下载,web开发资源,技术博客
}NtM易塔云建站-模板下载,web开发资源,技术博客
}
思路二:链表入栈。先进先出。在要把n节点入栈之前,n节点就是要删除的节点,上一个已经入栈的节点,就是待删除节点的前驱结点。
public ListNode removeNthFromEnd(ListNode head, int n) {NtM易塔云建站-模板下载,web开发资源,技术博客
ListNode dummy = new ListNode(0, head);NtM易塔云建站-模板下载,web开发资源,技术博客
Deque<ListNode> stack = new LinkedList<ListNode>();NtM易塔云建站-模板下载,web开发资源,技术博客
ListNode curr = dummy;NtM易塔云建站-模板下载,web开发资源,技术博客
while (curr != null) {NtM易塔云建站-模板下载,web开发资源,技术博客
stack.push(curr);NtM易塔云建站-模板下载,web开发资源,技术博客
curr = curr.next;NtM易塔云建站-模板下载,web开发资源,技术博客
}NtM易塔云建站-模板下载,web开发资源,技术博客
for(int i=0; i<n; ++i) {NtM易塔云建站-模板下载,web开发资源,技术博客
stack.pop();//把后来的,大于等于n的节点都弹出去,弹到哪了不知道NtM易塔云建站-模板下载,web开发资源,技术博客
}NtM易塔云建站-模板下载,web开发资源,技术博客
ListNode prev = stack.peek();NtM易塔云建站-模板下载,web开发资源,技术博客
prev.next = prev.next.next;NtM易塔云建站-模板下载,web开发资源,技术博客
return dummy.next;NtM易塔云建站-模板下载,web开发资源,技术博客
}