最後からn番目のノードを削除

3963 ワード

C/C++

問題は、最後からn番目のノードを削除することを示す.Given a linked list, remove the n th 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.

問題分析1 dummyノードを新規作成し、チェーンテーブルをdummy後に掛け、チェーンテーブルヘッダhead=dummyとする.2 frontとbackポインタはそれぞれheadに割り当てられ、frontを先にnステップさせる.③両ポインタを後ろに移動し、frontがチェーンテーブルの末尾を指す場合、back->nextが指すノードは削除するノードである.④back->next=back->next->nextとし、head->nextを返します.ps:チェーンヘッダをdummyの後ろに掛けるのは、削除するノードを処理するためにヘッダノードが接続されている場合です.

コード実装

/**
 * 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(NULL == head || n <= 0)
            return head;

        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        ListNode *front = head;//       ，   n 
        ListNode *back = head;//    
        while(n--)
        {
            front = front->next;
        }
        while(front->next)
        {
            front = front->next;
            back = back->next;
        }//  back->next        
        back->next = back->next->next;//           

        return head->next;
    }
};

別の方法

ListNode *removeNthFromEnd(ListNode *head, int n) {
        if(NULL == head || n <= 0)
            return head;

        //  n ，    NULL，         
        ListNode *front = head;
        while(n--)
        {
            front = front->next;
        }
        if(NULL == front)
            return head->next;

        ListNode *back = head;
        while(front->next)
        {
            front = front->next;
            back = back->next;
        }
        back->next = back->next->next;

        return head;
    }

leetcode 486. Predict the Winner

spark sqlでhiveのtableにinsertするには