鏈表練習(xí)記錄：
19.刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)力扣
題目描述：
刪除單向鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)，例如：
輸入：1->2->3->4->NULL刪除倒數(shù)第二個(gè)節(jié)點(diǎn)，即刪除節(jié)點(diǎn)3輸出：1->2->3->NULL
思路：
方法一：先遍歷鏈表，得到節(jié)點(diǎn)數(shù)，正向遍歷到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
方法二：雙指針，只要兩個(gè)指針的間隔為n，就可以找到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，這里為了方便頭節(jié)點(diǎn)的處理，使用了一個(gè)虛擬頭結(jié)點(diǎn)。將兩個(gè)指針，first，second同時(shí)指向虛擬節(jié)點(diǎn)，讓first節(jié)點(diǎn)先走n個(gè)節(jié)點(diǎn)使得兩個(gè)節(jié)點(diǎn)的間隔為n，讓后兩個(gè)節(jié)點(diǎn)同時(shí)往后走，直到first節(jié)點(diǎn)到鏈表尾部（NULL），此時(shí)second節(jié)點(diǎn)位于待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
代碼實(shí)現(xiàn)：
刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
#include/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode {int val;struct ListNode *next;};struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {int loopNum = 0;int sum = 0;struct ListNode* node = head;while (node != NULL){node = node->next;sum++;}if ((head != NULL )&&( sum ==1) && (n == 1)){return NULL;}if (sum == n){head = head->next;return head;}node = head;for (loopNum;loopNumnext;}node->next = node->next->next;return head;}struct ListNode* removeNthFromEnd1(struct ListNode* head, int n) {struct ListNode* dummy = malloc(sizeof(struct ListNode));dummy->val = 0, dummy->next = head;struct ListNode* first = dummy;struct ListNode* second = dummy;for (int i = 0; i next;}while (first) {first = first->next;second = second->next;}second->next = second->next->next;struct ListNode* ans = dummy->next;free(dummy);return ans;}int main(){struct ListNode node3;node3.val = 3;node3.next = NULL;struct ListNode node2;node2.val = 2;node2.next = &node3;struct ListNode node1;node1.val = 1;node1.next = &node2;struct ListNode* result = removeNthFromEnd1(&node1,2);while (result != NULL){printf(“val = %d”, result->val);result = result->next;}return 0;}
