首页 > c/c++, LeetCode, 面试 > LeetCode面试题之删除单链表中倒数第n个节点

LeetCode面试题之删除单链表中倒数第n个节点

2016年7月15日 721 人阅读 发表评论 阅读评论

1. 限制于要求

  • 空间复杂度O(1),时间复杂度度O(n)

2.思考

可以使用两个指针来实现,一个cur指针先从链表头往后遍历n个节点,然后一个pre指针(初始为NULL)和cur指针一起在链表中往后遍历直到cur指向NULL,而此时pre指向的就是要被删除的倒数第n个节点的前驱,如果pre为空,则说明要删除的是链表头节点,否则更新一下pre的next指针即可,即pre->next = pre->next->next。

2.1删除链表尾节点

  • 初始状态

  • cur先向后遍历以1个节点
  • pre和cur一起向后遍历,直到cur指向NULL

  • pre不为空,更新pre的next指针,pre->next = pre->next->next

2.2删除链表中间节点

  • 初始状态
  • cur先向后遍历以2个节点
  • pre和cur一起向后遍历,直到cur指向NULL
  • pre不为空,更新pre的next指针,pre->next = pre->next->next

2.3删除链表头节点

  • 初始状态
  • cur先向后遍历以2个节点
  • pre和cur一起向后遍历,直到cur指向NULL
  • pre为空,要删除是头节点,head = head->next

3.代码

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (NULL == head) return NULL;          //空直接返回空
        if (NULL == head->next) return NULL;    //剪枝,优化算法,(链表中只有一个节点,然后要删除第一个节点)

        ListNode * pre = NULL;
        ListNode * cur = head;

        while (n--) cur = cur->next;

        while (cur)
        {
            pre = pre ? pre->next : head;
            cur = cur->next;
        }

        pre ? pre->next = pre->next->next : head = head->next;

        return head;
    }
};

4.OJ练习

LeetCode:https://leetcode.com/problems/remove-nth-node-from-end-of-list/

分类: c/c++, LeetCode, 面试 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.