算法题--删除链表的倒数第N个节点 [LeetCode]
题目描述
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
题解
方法一:两次扫描法
我们注意到这个问题可以容易地简化成另一个问题:删除从列表开头数起的第 (L - n + 1) 个结点,其中 L 是列表的长度。只要我们找到列表的长度 L,这个问题就很容易解决。
public static ListNode removeNthFromEnd(ListNode head, int n) {
if(n < 1){
return head;
}
ListNode node = head;
int len = 0;
while(node != null){
len ++;
node = node.next;
}
int index = len - n + 1;
if(index < 1){
return head;
}
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
node = dummyNode;
while(index > 1){
node = node.next;
index --;
}
node.next = node.next.next;
return dummyNode.next;
}
复杂度分析:
- 时间复杂度:O(L),算法对列表进行了两次遍历,首先计算了列表的长度 L,其次找到第 (L - n + 1)个结点。 操作执行了 2L-n+1 步,时间复杂度为 O(L)。
- 空间复杂度:O(1)。
方法二:一次扫描法
上述算法可以优化为只使用一次遍历。使用两个节点,一个是left一个是right。先让right走n步,然后再让left和right同时往前走,当right走到头时,left即是倒数第n个节点了。
public static ListNode removeNthFromEnd2(ListNode head, int n) {
if(n < 1){
return head;
}
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode leftNode = dummyNode;
ListNode rightNode = dummyNode;
while(rightNode.next != null){
if(n > 0){
rightNode = rightNode.next;
n--;
}else{
leftNode = leftNode.next;
rightNode = rightNode.next;
}
}
leftNode.next = leftNode.next.next;
return dummyNode.next;
}
复杂度分析:
- 时间复杂度:O(L)。算法对含有 LL 个结点的列表进行了一次遍历。
- 空间复杂度:O(1)。
题目地址:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/