LeetCode 19. Remove Nth Node From End of List（删除链表中倒数第N个节点）

题意：删除链表中倒数第N个节点。

法一：递归。每次统计当前链表长度，如果等于N，则return head -> next，即删除倒数第N个节点；否则的话，问题转化为子问题“对head->next这个链表删除倒数第N个节点”，将head的next指针指向该子问题的结果，返回head即可。这个方法时间复杂度高，不推荐。

/**

 * 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 == NULL) return NULL;

        int cnt = 0;

        ListNode *tmp = head;

        while(tmp){

            ++cnt;

            tmp = tmp -> next;

        }

        if(cnt == n){

            return head -> next;

        }

        head -> next = removeNthFromEnd(head -> next, n);

        return head;

    }

};

法二：快慢指针，快指针先比慢指针多走N步，然后两者同时走，这样的话，当快指针的next指向NULL时，说明慢指针的next指向要被删除的节点。

注意：fast先走n步后，如果为NULL，表示链表长为n，则直接删除头结点，返回head->next即可。

/**

 * 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* fast = head;

        ListNode* slow = head;

        while(n--){

            fast = fast -> next;

        }

        if(fast == NULL) return head -> next;

        while(fast -> next){

            fast = fast -> next;

            slow = slow -> next;

        }

        slow -> next = slow -> next -> next;

        return head;

    }

};

巴特西

LeetCode 19. Remove Nth Node From End of List（删除链表中倒数第N个节点）

最新文章

热门文章