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

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

原文 http://blog.csdn.net/huangfei711/article/details/79253706

2018-02-05 02:00:31阅读(457)

资源来源于 LeetCode 19 —— Remove Nth Node From End of List。题目描述如下所示:
删除链表中<a href=倒数第n个节点时间复杂度为O(n))" src="http://img.blog.csdn.net/20180204171441806?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaHVhbmdmZWk3MTE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="这里写图片描述" title="">

题目意思很简单,简而言之就是删除链表中倒数第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;
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹