19删除链表的倒数第n个结点

正常思路，先遍历一遍链表得到长度，然后进行第二次遍历得到待删除结点的上一个结点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        
        int l = 0;

        while( cur->next != nullptr )
        {
            l++;
            cur = cur->next;
        }
        
        if(l==1)
         return nullptr;
         else
         {
            //找到待删除结点的上一个结点，如果是删除链表第一个结点，则不移动cur，因此cur初始为dummyHead
			cur = dummyHead;
            for(int i=0; i<(l-n); i++)
            {
                cur = cur->next;
            }
             cur->next = cur->next->next;
             
              return dummyHead->next;
         }
        
    }
};

进阶:使用一遍循环。
其实就是想办法在不知道链表长度的情况下找到待删除结点前一个结点，将链表分为三段：l-n-1 1 n。 虽然不知道l的值，但是可以利用通过双指针的方式遍历链表剩余部分的方式来得到这个长度。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* left = dummyHead;
        ListNode* right = dummyHead;

        //right指向第n个结点
        while(n-- && right->next != nullptr )
        {
            right = right->next;
        }

        //left与right移动相同的步长
        //为了删除，left应该指向第l-n-1个结点
        //若使right还能移动l-n-1，则还需要移动一步
        right = right->next;
        while(right != nullptr)
        {
            right = right->next;
            left = left->next;
        }
        left->next = left->next->next;
        return dummyHead->next;
    }
};