LeetCode刷题——算法学习计划（入门部分）

文章目录

• 题目描述
• 思路介绍
• 我的第一次正确提交
• 官方版本
• • 方法一：计算链表长度
  • 方法二：栈
  • 方法三：双指针

题目描述

思路介绍

个人思路：先求出要删除的结点是该链表的第几个结点（index=len + 1 -n），如果是第一个结点（head），就将head往右移动（head=head->next）；如果不是头结点，就用一个链表指针tmp指向要删除的结点的上一个结点，最后将tmp的下一个结点的下个结点接在tmp的后面（tmp->next=tmp->next->next）。

我的第一次正确提交

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//获取链表长度
int GetListNodeLen(struct ListNode* head)
{
    int len = 1;
    struct ListNode *tmp = head; 
    if(tmp == NULL)
        return 0;
    while(tmp->next != NULL)
    {
        len++;
        tmp = tmp->next;
    }
    return len;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    int i = 0;
    struct ListNode *tmp = head; 
    int len = GetListNodeLen(head);   //获取链表长度
    int index = len + 1 - n;          //要删除的链表结点序号（从1开始）
    if(index == 1)                    //如果要删除的为头结点
    {
        head = head -> next;
        return head;
    }
    for(i = 1; i < index - 1; i++)    //将tmp移动到要删除结点的前一个结点
    {
        tmp = tmp->next;
    }
    tmp->next = tmp->next->next;      //将要删除结点的下一个结点接在它前一个结点后面
    return head;
}

官方版本

下面是官方版本

方法一：计算链表长度

一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1 个节点时，它就是我们需要删除的节点。
为了与题目中的 n 保持一致，节点的编号从 1 开始，头节点为编号 1 的节点。
为了方便删除操作，我们可以从哑节点开始遍历 L−n+1 个节点。当遍历到第 L−n+1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。
——作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/

这也就是我所用的方法，但这里用到了哑节点(dummy->val = 0, dummy->next = head;)

int getLength(struct ListNode* head) {
    int length = 0;
    while (head) {
        ++length;
        head = head->next;
    }
    return length;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    int length = getLength(head);
    struct ListNode* cur = dummy;
    for (int i = 1; i < length - n + 1; ++i) {
        cur = cur->next;
    }
    cur->next = cur->next->next;
    struct ListNode* ans = dummy->next;
    free(dummy);
    return ans;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(1)。

方法二：栈

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。
——作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/

struct Stack {
    struct ListNode* val;
    struct Stack* next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    struct Stack* stk = NULL;
    struct ListNode* cur = dummy;
    while (cur) {
        struct Stack* tmp = malloc(sizeof(struct Stack));
        tmp->val = cur, tmp->next = stk;
        stk = tmp;
        cur = cur->next;
    }
    for (int i = 0; i < n; ++i) {
        struct Stack* tmp = stk->next;
        free(stk);
        stk = tmp;
    }
    struct ListNode* prev = stk->val;
    prev->next = prev->next->next;
    struct ListNode* ans = dummy->next;
    free(dummy);
    return ans;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(L)，其中 L 是链表的长度。主要为栈的开销。

方法三：双指针

我们也可以在不预处理出链表的长度，以及使用常数空间的前提下解决本题。具体思路见官方题解

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    struct ListNode* first = head;
    struct ListNode* second = dummy;
    for (int i = 0; i < n; ++i) {
        first = first->next;
    }
    while (first) {
        first = first->next;
        second = second->next;
    }
    second->next = second->next->next;
    struct ListNode* ans = dummy->next;
    free(dummy);
    return ans;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(1)。

下面是我的失败的提交记录

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//获取链表长度
int GetListNodeLen(struct ListNode* head)
{
    int len = 1;
    struct ListNode *tmp = head; 
    if(tmp == NULL)
        return 0;
    while(tmp->next != NULL)
    {
        len++;
        tmp = tmp->next;
    }
    return len;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    int i = 0;
    struct ListNode *tmp = head; 
    int len = GetListNodeLen(head);   //获取链表长度
    int index = len + 1 - n;          //要删除的链表结点序号（从1开始）
    if(index == 1)                    //如果要删除的为头结点
    {
        tmp = tmp -> next;
        return head;
    }
    for(i = 1; i < index - 1; i++)    //将tmp移动到要删除结点的前一个结点
    {
        tmp = tmp->next;
    }
    tmp->next = tmp->next->next;      //将要删除结点的下一个结点接在它前一个结点后面
    return head;
}

这份代码其实和提交成功的版本就两行不同：(前面有struct ListNode *tmp = head;)

错误代码

    if(index == 1)                    //如果要删除的为头结点
    {
        tmp = tmp -> next;
        return head;
    }

提交成功的版本，对比之下，发现上面那种写法，head被我覆盖掉了。。。。【可以没有头结点，但不能没有头指针】
这个错误可以通过官方题解中的哑节点避免，那样就不用进行下面这个判断了。

    if(index == 1)                    //如果要删除的为头结点
    {
        head = head -> next;
        return head;
    }