删除链表中倒数第n个节点(时间复杂度为O(n))

2018-02-05 10:33:03来源:网络收集作者:程序诗人人点击

分享

资源来源于 LeetCode 19 —— Remove Nth Node From End of List。题目描述如下所示:
删除链表中倒数第n个节点(时间复杂度为O(n))


题目意思很简单,简而言之就是删除链表中倒数第n个节点,需要注意的是(图中红框标出),只能遍历一次链表。还有一点,n一定是有效的,即n不会大于链表中的元素总数。我们首先要考虑的时,如何找到倒数第n个节点,由于只允许一次遍历,所以我们不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该移除了。那么我们需要用两个指针来帮助我们解题,pre 和 cur 指针。首先 cur 指针先向前走 n 步,如果此时 cur 指向空,说明 n 为链表的长度,则需要移除的为首元素,那么此时我们返回 head->next 即可,如果 cur 存在,我们再继续往下走,此时 pre 指针也跟着走,直到 cur 为最后一个元素时停止,此时 pre 指向要移除元素的前一个元素,我们再修改指针跳过需要移除的元素即可。这就是算法的巧妙之处,比起普普通通对链表的两次遍历,该算法效率显然更好。


代码示例如下:


struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head -> next == NULL) {
return NULL;
}
ListNode *pre = head;
ListNode *cur = head;
for (int i = 0; i < n; i ++) {
cur = cur -> next;
}
if (cur == NULL) {
return head -> next;
}
while (cur -> next != NULL) {
cur = cur -> next;
pre = pre -> next;
}
pre -> next = pre -> next -> next;
return head;
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台