Day88 | 灵神 | 前后指针 移除链表元素 从链表中移除结点

2487.从链表中移除结点

2487. 从链表中移除节点 - 力扣（LeetCode）

迭代

思路：

凡是你觉得反转链表以后好做的都要毫不犹豫反转链表

这道题是因为如果左边的数都比右边这一个数小的话，我们很难找到从哪个结点开始删除

比如[1,2,3,4,5,6,7,8,9,13]，1-9全是要删的，我们不知道从哪里开始进行循环

但是反转以后就很简单了

[13,1,2,3,4,5,6,7,8,9]，13之后都是要删的，而且13可作为要删除节点的前一个结点，所以翻转后会好做很多

到这里也知道了其实这道题是倒着找最大值，所以反转后会比较好做，因为反转后变成正着找最大值

完整代码：

class Solution {
public:
    //206.反转链表
    ListNode *reverseList(ListNode *head) {
        ListNode *pre = nullptr, *cur = head;
        while (cur) {
            ListNode *nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
    ListNode* removeNodes(ListNode* head) {
        //反转链表
        ListNode *head2=reverseList(head);
        ListNode *t=head2;
        //循环，如果下一个结点的值小于当前结点，那就该删，否则就继续遍历
        while(t->next)
        {   
            if(t->val>t->next->val)
            {
                ListNode *p=t->next;
                t->next=t->next->next;
            }
            else
                t=t->next;
        }
        //再次反转链表得到答案
        return reverseList(head2);
    }
};

递归

思路：

灵神：既然要倒着看最大值，那么用递归解决是最合适的，毕竟递归本质就是在倒着遍历链表。

笔者第一次拿递归做链表的题所以还不太熟练，尝试写写题解

1.递归函数的意义

把以传入参数head为首的单链表修改为符合题目条件的链表，即移除节点后的链表

2.参数和返回值

参数就是head，表示这层递归函数要遍历的单链表的首结点

返回值就是修改后链表的首结点 即ListNode*

ListNode *removeNodes(ListNode *head)

3.终止条件

如果head->next为空，说明没有结点需要遍历了，返回nullptr

if (head->next == nullptr) {
	return head;
}

4.本层逻辑

因为要倒着遍历链表，所以要先遍历后续节点

依次遍历直到最后一个结点，此时head和node的值都是head

然后逐层向上层递归函数返回

以[5,2,13,3,8]为例子

head=8，node=8  不删除8直接返回head
head=3，node=8  删除3，即直接返回node
head=13,node=8  不删除head
head=2,node=13   删除2

注：1.要删除head时，直接返回node就相当于把head给删掉了

2.如果删除了结点head，那么head->next=node就是在连接单链表

ListNode *node = removeNodes(head->next); // 返回的链表头一定是最大的
      if (node->val > head->val) {
          return node; // 删除 head
      }
      head->next = node; // 不删除 head
      return head;

完整代码：

class Solution {
public:
    ListNode *removeNodes(ListNode *head) {
        if (head->next == nullptr) {
            return head;
        }
        ListNode *node = removeNodes(head->next); // 返回的链表头一定是最大的
        if (node->val > head->val) {
            return node; // 删除 head
        }
        head->next = node; // 不删除 head
        return head;
    }
};