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;}