删除右侧上具有较大值的节点
给定一个单独链接的列表，删除右侧具有较大值的所有节点。
示例：
a( 列表12->15->10->11->5->6->2->3->NULL应更改为15->11->6->3->NULL。请注意，12、10、5和2已被删除，因为右侧有一个较大的值。
当我们检查12时，我们发现在12之后有一个节点的值大于12(即15(，因此我们删除12。当我们检查15时，在15之后没有发现值大于15的节点，所以我们保留这个节点。当我们这样做时，我们会得到15->6->3
b( 列表10->20->30->40->50->60->NULL应更改为60->NULL。请注意，10、20、30、40和50已被删除，因为它们在右侧的值都较大。
c( 不应更改列表60->50->40->30->20->10->NULL。
我已经为它编写了函数。但它不起作用。
void remove_lower(struct node** head_ref)
{
struct node* current = (*head_ref);
if(current != NULL && current->next != NULL)
return ;
struct node* temp;
while(current->next != NULL)
{
if(current->data > current->next->data)
{
temp = current->next;
current = temp->next;
free(temp);
}
else
current = current->next;
}
}
您应该跟踪"上一个"项目并更新其"下一个"指针，否则您将在删除一些不是列表中第一个的元素时破坏列表。此外，您的算法会删除所有"下一个"元素，这些元素比当前元素"大"。根据你的描述，如果"当前"元素的右侧有一个更大的元素，你将删除它。所以您应该删除"当前"元素，而不是下一个元素。
我建议对该算法(不幸的是，O(N^2)(采用以下方法(在ideone上检查(：
void remove_lower(struct node** head_ref)
{
struct node* current = (*head_ref);
if(current == NULL || current->next == NULL)
return ;
struct node* prev = NULL, *next = NULL, *temp = NULL;
while(current->next != NULL)
{
next = current->next;
temp = next;
/* check if there is any element greater than current */
while(temp->next != NULL) {
if (temp->data > current->data) {
/*
* if some element is greater than current, then
* delete current element
*/
free(current);
current = NULL;
if (prev == NULL) {
/* it was the first element, need to update the head */
*head_ref = next;
} else {
prev->next = next;
}
break;
}
temp = temp->next;
}
/* if current element was not deleted */
if (current != NULL) {
prev = current;
}
current = next;
}
}
输出：
输入数据：
2->7->1->36->6->0->5->-1->16->4->-2->3->-3->4->2->-4->1->-5->0->0->NULL
输出数据：
36->16->4->4->2->1->0->0->NULL
您似乎已经颠倒了if语句中的条件。
if(current != NULL && current->next != NULL)
return ;
更改为：
if (current == NULL || current->next == NULL)
return ;
另一个：
if(current->data > current->next->data)
{
更改为：
if(current->data < current->next->data)
{
这不是你的意思吗？
if(current == NULL || current->next == NULL)
return ;
算法这是我的算法，时间复杂度为O(n)
-
反转列表。
-
遍历反向列表。保持最大值直到现在。如果下一个节点<max，然后删除下一个节点，否则max=下一个结点。
-
再次反转列表以保留原始顺序。
void reverseList(struct node **headref); void _delLesserNodes(struct node *head); /* Deletes nodes which have a node with greater value node on left side */ void delLesserNodes(struct node **head_ref) { /* 1) Reverse the linked list */ reverseList(head_ref); /* 2) In the reversed list, delete nodes which have a node with greater value node on left side. Note that head node is never deleted because it is the leftmost node.*/ _delLesserNodes(*head_ref); /* 3) Reverse the linked list again to retain the original order */ reverseList(head_ref); } /* Deletes nodes which have greater value node(s) on left side */ void _delLesserNodes(struct node *head) { struct node *current = head; /* Initialize max */ struct node *maxnode = head; struct node *temp; while (current != NULL && current->next != NULL) { /* If current is smaller than max, then delete current */ if(current->next->data < maxnode->data) { temp = current->next; current->next = temp->next; free(temp); } /* If current is greater than max, then update max and move current */ else { current = current->next; maxnode = current; } } } //*********************************************** void reverseList(struct node **headref) { struct node *current = *headref; struct node *prev = NULL; struct node *next; while(current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *headref = prev; }
如果有任何错误，请告诉我。
if(current != NULL && current->next != NULL)
return ;
我觉得你有问题。这在第一步中退出。你可能想写
if(current == NULL || current->next == NULL)
return ;
如果您告诉我们更多不起作用的内容，例如输入和输出、编译器错误或调试器堆栈争用，将非常有用。
也就是说，我看到，如果下一个值小于当前值(即其前身，其"左"(，则您将删除该值，据我所知，这不是要求。如果当前小于下一个，您不应该根据要求删除它吗？
不需要反转也可以完成。
这是代码
public void delNodes(Node n){
Node curr = n;
while(curr != null && curr.next != null){
if(curr.data < curr.next.data){
Node temp = curr.next;
curr.data = temp.data;
curr.next = temp.next;
temp = null;
}else{
curr = curr.next;
}
}
}
如果有人在寻找python实现：
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printList(self):
temp = self.head
while (temp):
print(temp.data, end=" ")
temp = temp.next
print()
def delete_nodes_with_larger_right(llist):
current = llist.head
prev = llist.head
max = current.data
while (current is not None):
if current.data >= max:
max = current.data
prev = current
current = current.next
else:
prev.next = current.next
current.next = None
current = prev.next
return
def reverse(llist):
current = llist.head
next = None
prev = None
while (current is not None):
next = current.next
current.next = prev
prev = current
current = next
llist.head = prev
if __name__ == '__main__':
values_list = [[12, 15, 10, 11, 5, 6, 2, 3], [10, 20, 30, 40, 50, 60], [60, 50, 40, 30, 20, 10]]
t = len(values_list)
for index in range(t):
llist = LinkedList()
for i in values_list[index]:
llist.push(i)
delete_nodes_with_larger_right(llist)
reverse(llist)
llist.printList()
t -= 1
根据您的测试用例更改values_list中的输入。
输入：
12 15 10 11 5 6 2 3
10 20 30 40 50 60
60 50 40 30 20 10
输出：
15 11 6 3
60
60 50 40 30 20 10