C++程序 删除右侧具有较大值的节点

在链表操作中，有时需要删除链表中一些具有特定规律或特征的节点。例如，在一个单链表中，删除右侧具有较大值的节点，即删除链表中比当前节点大的所有节点。本文将介绍如何使用C++编写程序实现这一操作。

算法思路

本问题可以使用双指针法解决。定义两个指针，一个指向当前节点，一个指向下一个节点，比较当前节点与下一个节点的数值大小，如果下一个节点的值较大，那么删除该节点，否则保留该节点。继续这个过程，直到到达链表的末尾。

代码实现

首先，我们需要定义一个链表节点结构体，包含节点值和指向下一个节点的指针。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

接下来，我们编写删除右侧较大值节点的函数。其中，使用了双指针法，依次比较当前节点与下一个节点的值大小，并删除右侧节点。

ListNode* deleteRightMax(ListNode* head) {
    if(head == NULL) return head;
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* cur = head;
    ListNode* nxt = head->next;
    while(nxt != NULL) {
        if(nxt->val > cur->val) {
            cur->next = nxt->next;
            nxt = nxt->next;
            // 如果删除最后一个节点，则修改cur指针位置
            if(cur->next == NULL) cur = dummy;
        } else {
            cur = nxt;
            nxt = nxt->next;
        }
    }
    return dummy->next;
}

接下来，我们来测试一下这个函数。下面是一个例子：

int main() {
    ListNode* head = new ListNode(4);
    head->next = new ListNode(3);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(1);

    cout << "Before deleting right max nodes:" << endl;
    ListNode* p = head;
    while(p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    ListNode* newHead = deleteRightMax(head);

    cout << "After deleting right max nodes:" << endl;
    ListNode* q = newHead;
    while(q != NULL) {
        cout << q->val << " ";
        q = q->next;
    }
    cout << endl;

    return 0;
}

输出结果如下：

Before deleting right max nodes:
4 3 2 1
After deleting right max nodes:
4 3 

可以看到，原链表中比4大的节点都被删掉了。

结论

通过双指针法，我们可以轻松地实现删除右侧较大值节点的函数。这个方法的时间复杂度为O(N)，空间复杂度为O(1)。在链表操作中，这个方法是十分高效的，也是十分实用的。