19. Remove Nth Node From End of List 移除链表倒数第N个节点

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid. Try to do this in one pass.

Difficulty: Medium

这道题让我们溢出链表中第N个节点,并制定n为有效的,就是n不会大于链表元素的总个数.看网上说这道题在问的时候可能会加上限制在一次循环的条件完成.如果用一次循环完成的话,就不能单独用一次循环来求链表元素的个数,要在循环到要删除的元素的位置时就该删除该元素.所以需要一点技巧. 我们可以定义两个指针pre,cur.先让cur前进N步,如果此时cur指向的为NULL,说明该链表的长度为N,所以移除首个元素就可以.如果cur指向的不为NULL,那么此时同时让pre,cur同时前进,直到cur指向最后一个元素,此时pre指向的就是倒数第N个元素,删除即可.

剑指offer 56题与这道题稍微有点像,可以一起看下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head->next) return NULL;
        ListNode* pre = head,*cur = head;
        for (int i = 0;i < n;i++) cur = cur->next;
        if (!cur) {
            ListNode* res = head->next;
            delete head;
            head = NULL;
            return res;
        }
        while (cur->next){
            cur = cur->next;
            pre = pre->next;
        }
        ListNode* delNode = pre->next;
        delete delNode;
        delNode = NULL;
        pre->next = pre->next->next;
        return head;
    }
};
 
comments powered by Disqus