[leetcode] 19 remove Nth node fr

Given a linked list, remove the n-th node from the end of list and return its head.
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.

删除单链表倒数第N个元素

这题 就是弄俩指针left, right
想办法让 left 扮演 倒数第n+1个节点
让right 扮演倒数第一个节点
思路很容易想到， 主要就是有个链表长度为N的情况要单独处理。

步骤

1. 让 right 先left 右移 n次
2. 处理 如果链表长度为n时的特殊情况（毕竟此时 right 已经跑出界了）， 直接返回head->next
   3.同时右移 left ，right 直到 right 等于最后一个节点
   4.此时 left就是倒数第n+1个节点 让n+1直接指向倒数第n-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) {
        ListNode* left = head;
        ListNode* right = head;
        
        if (!head->next || ! head){
            return NULL;
        }
        
        // 右边的 比 左边的 多走  n次
        while (n){
            right = right->next;
            n--;
        }
        
        // cornor  case 
        // 链表长度正好为n 直接删去头节点
        if (!right){
            return head->next;
        }
        
        // left--> -(n+1) 
        // right --> -1
        while(right->next){
            left = left->next;
            right = right->next;
        }
        //temp --> -(n-1)
        // remove -n  == -(n+1)  -> -(n-1)
        ListNode* temp = left->next->next;
        left->next = temp;
        return head;

        
    }
};