【每日一题】从链表中移除节点

发布时间:2024年01月03日

Tag

【递归】【栈】【链表】【2024-01-03】


题目来源

2487. 从链表中移除节点


解题思路

本题的解题思路有很多,比如模拟的想法:

  • 首先找出每个节点右侧比它大的节点值,用数组存储起来;
  • 接着遍历链表,如果当前节点小于当前节点右侧的节点值,则移除当前节点。

该模拟的方法应该是比较容易理解的,但是实现起来相对复杂。其中需要更新节点右侧最大节点值数组,比较容易实现的方法从右到左(从根节点到头结点)遍历链表节点来更新数组。但是单向链表是从头结点到尾节点连接的,于是更新右侧最大节点值数组又有以下两种实现方法:

  • 预先将链表值存储到数组中,这样就可以对链表值数组从右到左处理来得到右侧最大节点值数组,时间复杂度为 O ( n ) O(n) O(n),为了得到右侧最大节点值数组需要一个额外的长度为 n 的空间;
  • 将链表从左到右的节点值入栈,在出栈的过程中计算得到右侧最大节点值数组。

该模拟的方法实现起来相对繁琐,最后会给出实现代码。

接下来主要研究以下方法,这些方法是我一开始没想到的方法:

  • 递归;
  • 栈;
  • 反转链表。

方法一:递归

思路

递归的方法你想到了就很简单,没想到那就需要多练、多观察是否是子问题。

由题意可知,节点对它右侧的所有节点都没有影响,因此对于某一节点,我们可以对它的右侧节点递归地进行移除操作:

  • 该节点为空,那么递归函数返回空指针。
  • 该节点不为空,那么先对它的右侧节点进行移除操作,得到一个新的子链表,如果子链表的头节点值大于该节点的值,那么移除该节点,否则将该节点作为子链表的头节点,最后返回该子链表。

算法

class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        head->next = removeNodes(head->next);
        if (head->next != nullptr && head->val < head->next->val) {
            return head->next;
        }
        else {
            return head;
        }
    }
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为链表节点个数。

空间复杂度: O ( 1 ) O(1) O(1)

方法二:栈

思路

使用栈来模拟递归:

  • 将所有链表节点从左到右压入栈中,同时更新初始链表为空;
  • 不断从栈中弹出节点,如果节点的值大于等于先链表的头节点,那么将该节点插入先链表的头部,否则移除该节点。

算法

class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        stack<ListNode*> st;
        for(; head != nullptr; head = head->next) {
            st.push(head);
        }
        for (; !st.empty(); st.pop()) {
            if (head == nullptr || st.top()->val >= head->val) {
                st.top()->next = head;
                head = st.top();
            }
        }
        return head;
    }

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为链表节点个数。

空间复杂度: O ( n ) O(n) O(n)

方法三:反转链表

思路

方法一和方法二都是从右到左进行移除,然后对于单链表来说,从左到右更高效,因此我们可以先对链表进行反转。问题转化为:给定一个链表,移除每一个左侧有一个更大数值的节点。

对于以上问题,我们可以从左到右对链表进行遍历,对于当前访问的节点:

  • 不断地移除该节点的右侧节点,直到该节点的右侧节点值大于或等于该节点值。
  • 访问下一节点。

最后对剩余的链表进行再一次反转,即为结果。

算法

class Solution {
public:
    ListNode *reverse(ListNode *head) {
        ListNode dummy;
        while (head != nullptr) {
            ListNode *p = head;
            head = head->next;
            p->next = dummy.next;
            dummy.next = p;
        }
        return dummy.next;
    }

    ListNode* removeNodes(ListNode* head) {
        head = reverse(head);
        for (ListNode *p = head; p->next != nullptr; ) {
            if (p->val > p->next->val) {
                p->next = p->next->next;
            } else {
                p = p->next;
            }
        }
        return reverse(head);
    }
};

方法四:模拟

算法

class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        vector<int> rightMaximumVal;
        stack<int> st;
        ListNode* node = head;
        for (; node != nullptr; node = node->next) {
            st.push(node->val);
        }
        int topVal;
        for (; !st.empty(); st.pop()) {
            if (rightMaximumVal.empty() || st.top() > topVal) {
               rightMaximumVal.push_back(st.top());
               topVal = st.top();
            }
            else {
                rightMaximumVal.push_back(topVal);
            }
        }
        reverse(rightMaximumVal.begin(), rightMaximumVal.end());

        int i = 0;
        ListNode* prev = new ListNode(-1);
        ListNode* newPrev = prev;
        for (; head != nullptr; head = head->next) {
            if (head->val >= rightMaximumVal[i++]) {
                prev->next = head;
                prev = head;
            }
        }
        return newPrev->next;
    }
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为链表节点个数。

空间复杂度: O ( n ) O(n) O(n)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

文章来源:https://blog.csdn.net/weixin_54383080/article/details/135356783
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。