19. 刪除鏈表的倒數(shù)第 N 個結點

難度中等2492

給你一個鏈表，刪除鏈表的倒數(shù)第?n?個結點，并且返回鏈表的頭結點。

?

示例 1：

輸入：head = [1,2,3,4,5], n = 2輸出：[1,2,3,5]

示例 2：

輸入：head = [1], n = 1輸出：[]

示例 3：

輸入：head = [1,2], n = 1輸出：[1]

?

提示：

• 鏈表中結點的數(shù)目為?sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

?

進階：你能嘗試使用一趟掃描實現(xiàn)嗎？

第一種錯法：

/**

?*?Definition?for?singly-linked?list.

?*?struct?ListNode?{

?*?????int?val;

?*?????struct?ListNode?*next;

?*?};

?*/

struct?ListNode*?removeNthFromEnd(struct?ListNode*?head,?int?n){

????struct?ListNode?*newhead?=?(struct?ListNode*)malloc(sizeof(struct?ListNode));

????newhead->next?=?head;

????struct?ListNode?*cur?=?newhead;

????struct?ListNode?*last?=?cur;

????while(1){

????????for(int?i=0;i<n;i++){

????????????last?=?last->next;

????????}

?????????if(last->next==NULL){

????????????struct?ListNode*?tmp?=?cur->next;

????????????cur->next?=?last;

????????????free(tmp);

????????????return?newhead->next;

????????}else{

????????????cur=cur->next;

????????????last?=?cur;

????????}

????}

}

這里的last是只考慮了n是偶數(shù)的情況，當n為奇數(shù)時last將指向需要刪除的元素，與循環(huán)中的代碼矛盾。

第一種對法：

/**

?*?Definition?for?singly-linked?list.

?*?struct?ListNode?{

?*?????int?val;

?*?????struct?ListNode?*next;

?*?};

?*/

struct?ListNode*?removeNthFromEnd(struct?ListNode*?head,?int?n){

????struct?ListNode?*newhead?=?(struct?ListNode*)malloc(sizeof(struct?ListNode));

????newhead->next?=?head;

????struct?ListNode?*cur?=?newhead;

????struct?ListNode?*last?=?cur;

????while(1){

????????for(int?i=0;i<=n;i++){

????????????last?=?last->next;

????????}

?????????if(last==NULL){

????????????struct?ListNode*?tmp?=?cur->next;

????????????cur->next?=?cur->next->next;

????????????free(tmp);

????????????return?newhead->next;

????????}else{

????????????cur=cur->next;

????????????last?=?cur;

????????}

????}

}