链表（1）

链表练习记录：

19.删除链表的倒数第 N 个结点力扣

题目描述：

删除单向链表的倒数第 N 个结点，例如：

输入：1->2->3->4->NULL删除倒数第二个节点，即删除节点3输出：1->2->3->NULL

思路：

方法一：先遍历链表，得到节点数，正向遍历到要删除节点的前一个节点

方法二：双指针，只要两个指针的间隔为n，就可以找到要删除节点的前一个节点，这里为了方便头节点的处理，使用了一个虚拟头结点。将两个指针，first，second同时指向虚拟节点，让first节点先走n个节点使得两个节点的间隔为n，让后两个节点同时往后走，直到first节点到链表尾部（NULL），此时second节点位于待删除节点的前一个节点。

代码实现：

删除链表的倒数第 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;}