C/C++教程

算法入门C——19. 删除链表的倒数第 N 个结点

本文主要是介绍算法入门C——19. 删除链表的倒数第 N 个结点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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;
    }
这篇关于算法入门C——19. 删除链表的倒数第 N 个结点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!