凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 19. Remove Nth Node From End of List

分类:algorithm| 发布时间:2016-07-04 23:24:00


题目

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.

题意

删除从末尾开始的第 N 个元素。

解法

/**
 * 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) {
        int size = 0;
        for (ListNode *tmp = head; tmp; tmp = tmp->next) {
            ++size;
        }

        if (size == n) {
            ListNode *tmp = head;
            head = head->next;
            delete tmp;
            return head;
        }

        int offset = size - n - 1;
        ListNode *tmp = head;
        for (; offset; --offset, tmp = tmp->next) ;
        ListNode *toDelete = tmp->next;
        tmp->next = toDelete->next;
        delete toDelete;
        return head;
    }
};