【LeetCode】 19. Remove Nth Node From End of List

Description

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

給一個linked list，移除掉從後面數過來第n個數字並回傳list的起點。

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.

Solution

• linked-list的題目，兩種解法，一種需要跑兩次list，一種只需要跑一次。
• 第一種：先得到list的長度，就可以知道由正向去找要刪掉哪一個數字了。
• 第二種：用兩個指標，先讓第一個跑n步，接著兩個一起跑，當第一個到底的時候，第二個所指的就是要移除的數字了。

Code

• 解法一：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* temp = head;
        int s=0;
        for(;temp;s++)
            temp=temp->next;
        
        n=s-n;
        temp = head;
        if(n==0) return head->next;
        
        for(int i=0;i<n-1;i++)
            temp = temp->next;
        
        if(temp->next)
            temp->next = temp->next->next;
        
        return head;
    }
};

• 解法二：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* first = head;
        for(int i=0;i<n;i++)
            first=first->next;
        
        if(!first)
            return head->next;
        
        ListNode* second = head;
        for(;first->next;first=first->next)
            second=second->next;
        
        if(second->next)
            second->next=second->next->next;
        
        return head;
    }
};

tags: LeetCode C++