力扣算法-Day9

19.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

思路：

?暴力解：

? ? ? ? 首先找到链表的长度、再去寻找倒数第n个节点去删除。

双指针：

????????如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

解法一：（暴力解）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode));
    cur->next = head;
    struct ListNode* p = cur;
    struct ListNode* q = cur;
    int count = 0;
    while (p && p->next) {
        p=p->next;
        count++;
    }
    for (int i=0; i<count-n+1; i++) {
        if (i==count-n) {
            cur->next = cur->next->next;
        }
        cur = cur->next;
    }
    return q->next;
}

?解法二：（双指针）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    //定义虚拟头节点dummy 并初始化使其指向head
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    //定义 fast slow 双指针
    struct ListNode* fast = head;
    struct ListNode* slow = dummy;

    for (int i = 0; i < n; ++i) {
        fast = fast->next;
    }
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;//删除倒数第n个节点
    head = dummy->next;
    free(dummy);//删除虚拟节点dummy
    return head;
}

这一期专栏记录将我每天的刷题，希望各位的监督，也希望和各位共勉。

追光的人，终会光芒万丈！！