Leetcode 19. Remove Nth Node From End of List

Tyan

发布于 2019-05-25 22:47:05

3780

发布于 2019-05-25 22:47:05

文章被收录于专栏：SnailTyan SnailTyanSnailTyan

文章作者：Tyan

博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

Version 1

/**
 * 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 || !head->next) {
            return nullptr;
        }
        int number = 0;
        ListNode* current = head;
        while(current) {
            if(current->next) {
                number += 2;
                current = current->next->next;
            }
            else {
                number += 1;
                current = current->next;
            }
        }
        int target = number - n;
        if(target == 0) {
            return head->next;
        }
        ListNode* pre = head;
        current = head->next;
        int count = 1;
        while(count != target) {
            pre = current;
            current = current->next;
            count++;
        }
        pre->next = pre->next->next;
        return head;
    }
};

Version 2

/**
 * 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 || !head->next) {
            return nullptr;
        }
        int number = 0;
        int count = 0;
        ListNode* middle = head;
        ListNode* current = head;
        while(current) {
            count++;
            middle = middle->next;
            if(current->next) {
                number += 2;
                current = current->next->next;
            }
            else {
                number += 1;
                current = current->next;
            }
        }
        int target = number - n;
        if(target == 0) {
            return head->next;
        }
        ListNode* pre = nullptr;
        int index = 0;
        if(target > count) {
            index = count;
            current = middle;
        }
        else {
            current = head;
        }
        while(index != target) {
            pre = current;
            current = current->next;
            index++;
        }
        pre->next = pre->next->next;
        return head;
    }
};

Version 3

/**
 * 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) {
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode* current = new_head;
        for(int i = 0; i < n + 1; i++) {
            current = current->next;
        }
        ListNode* pre = new_head;
        while(current) {
            current = current->next;
            pre = pre->next; 
        }
        pre->next = pre->next->next;
        return new_head->next;
    }
};