19. Remove Nth Node From End of List

• 第一种解法

  /**
   * 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 count = 0;
        ListNode* pre = head;  
        if(head == NULL)
        {
            return NULL;
        }
        
          while(pre != NULL)
        {
            count++;
            pre = pre->next;
              
        }
          
        if(count == n)  //删除头节点
        {
            pre = head;
            return pre->next;
        }
        
        pre = head;
          int i = 1;
        while(pre != NULL)
        {
            if(i == count - n)
            {
                break;
            }
            i++;
              pre = pre->next;
        }
        //删除一个节点
        ListNode* temp;
        temp = pre->next;
          
        pre->next = temp->next;
        delete temp;
        
        return head;
      }
  };

链表删除节点关键是找到待删除节点的前一个节点。另外就是注意要删除头节点的情况。在上面的代码中

        if(count == n)  //删除头节点
        {
            pre = head;
            return pre->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) 
        {
            int count = 0;
            ListNode* pre = head;  
            if(head == NULL)
            {
                return NULL;
            }
            
            while(pre != NULL)
            {
                count++;
                pre = pre->next;
            }
            
            if(count == n)  //删除头节点
            {
                pre = head;
                head = head->next;
                delete pre;
                return head;
            }
            
            pre = head;
             int i = 1;
            while(pre != NULL)
            {
                if(i == count - n)
                {
                    break;
                }
                i++;
                pre = pre->next;
            }
            //删除一个节点
            ListNode* temp;
            temp = pre->next;
            
            pre->next = temp->next;
            delete temp;
            
            return head;
        }
    };

• 快慢指针法

  声明一个快指针fast和一个慢指针slow。首先fast移动到待删除节点temp之前，然后fast和slow每次移动一步，当fast移动到最后时，slow指针正好移动到待删除节点temp之前，这时完成删除操作即可。

  /**
   * 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;
        }
        
        ListNode* newhead = new ListNode(0);
        newhead->next = head;
        
          ListNode* fast = newhead;
        ListNode* slow = newhead;
        
        for(int i = 0;i < n;i++)
        {
            fast = fast->next;  
        }
        
        while(fast->next)
        {
            fast = fast->next;
            slow = slow->next;
        }
        
        ListNode* temp = slow->next;  //temp表示待删除的节点
          slow->next = slow->next->next;
                
        delete temp;
        
        return newhead->next;
      }
  };

19. Remove Nth Node From End of List

原文：https://www.cnblogs.com/Manual-Linux/p/12115217.html