LeetCode刷题(18)【中等】删除链表的倒数第 N 个结点(C++)

简介: LeetCode刷题(18)【中等】删除链表的倒数第 N 个结点(C++)

@[TOC](删除链表的倒数第 N 个结点

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

在这里插入图片描述

题目——链接](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/))

遍历统计方法

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head)//空的直接返回
        {
            return NULL;
        }
        int count =  0;//统计个数
        ListNode* tempnode = head;
        ListNode* temp = NULL;
         int prev = 0;
        while(tempnode)
        {
            count++;
            tempnode = tempnode->next;
        }

        tempnode = head;
       
       //一共就一个,也一并算到删除第一个结点
        if(count == n)
        {
            temp = head;
            head = head->next;
            delete temp;
            return head;
        }
   
        //删除第一个结点之后的结点
        //循环拿到要删除结点的前一个结点
        while(prev != count -n)
        {
            prev++;
            //此时已经到了要删除结点的前一个结点,break
            if(prev == count-n)
            {
                break;
            }
            tempnode = tempnode->next;
        }
        //只有一个元素 or 删除第一个结点的时候得单独讨论,此方法不适用,越界了
        //由此可以理解为什么有的方法用了哨兵结点了,这样可以删除头结点
        temp =tempnode->next;
        tempnode->next = temp->next;
        delete temp;

        return head;

    }
};

哨兵结点

在上面方法的基础上加入一个哨兵结点。

哨兵结点的next指向head。

(LeetCode中的head都是带数据的)

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head)//空的直接返回
        {
            return NULL;
        }
        int count =  0;//统计个数
        int prev = -1;
        ListNode* temp = NULL;
        ListNode* tempHead = new ListNode;
        ListNode* tempnode = head;

        tempHead->next = head;
        while(tempnode)
        {
            count++;
            tempnode = tempnode->next;
        }

        tempnode = tempHead;
        while(prev !=count-n)
        {
            prev++;
            if(prev == count-n)
            {
                break;
            }
            tempnode =tempnode->next;
        }

        temp = tempnode->next;
        tempnode->next=  temp->next;
        delete   temp;
        return tempHead->next;

    }
};

快慢指针+哨兵结点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    //快慢指针都先指向新的头结点
    //快指针比慢指针先走n步
    //然后同时出发
    //当fast走到最后一个结点时,此时slow的下一个结点就是要删除的结点
    if(!head)
    {
        return NULL;
    }
    ListNode* tempHead = new ListNode;
    ListNode* temp = NULL;
    int count = 0;
    ListNode* slow = tempHead;
    ListNode* fast =tempHead;
    tempHead ->next = head;
    while(count != n)
    {
        fast = fast->next;
        count++;
    }    
    while(fast->next)
    {
        fast = fast->next;  
        slow = slow->next;
    }
    temp = slow->next;
    slow->next = temp->next;

    delete   temp;
    return tempHead->next;
}
};
相关文章
|
14天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
44 1
|
2月前
链表的中间结点
链表的中间结点
176 57
|
17天前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
13 0
|
3月前
|
算法
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点
|
3月前
【刷题记录】链表的回文结构
【刷题记录】链表的回文结构
|
3月前
|
机器学习/深度学习
【刷题记录】相交链表
【刷题记录】相交链表
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
5月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
5月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
41 2
|
6月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
48 1