遇到大于'x'的值时，如何删除链表右侧的所有节点？

Question

我在 Whosebug 上没有看到这个特定问题的解决方案。所以我发布这个。

我的需求是遇到大于'x'的值时，将链表右边的节点全部删除？例如

示例输入： 链表有值：5 1 2 6 和 x = 5
输出： 5 1 2

示例输入 链表有值：7 1 2 6 和 x = 6
输出： null（因为7大于6，应该删除右边的所有节点）

示例输入： 链表有值：5 4 7 6 和 x = 6
输出： 5 4

我想到了这个解决方案，但我正在努力寻找最佳解决方案

//head is the root node, nodes greater that "value" should be deleted
      Node Delete(Node head, int value) {
      // Complete this method

       Node cur = head;
       Node prev = null;    

      if(cur == null)
           return head;

     if(cur != null && cur.data > value )
       {
         while(cur != null)
         {
          prev = cur;
          cur = cur.next;
         }
          prev.next = cur;
          head = prev;
          return head;
       }
      else
      {
         while(cur != null && cur.data <= value)
         {
          prev = cur;     
          cur = cur.next;    
         }  
         if(cur != null && cur.data > value)
         { 
           while(cur != null)
           {          
               cur = cur.next;        
           }
           prev.next = cur;    
           return head;
         }    
          prev.next = null;       
          return head;       
      }   


    }

Answer 1

这是一个简单的 O(n) 解决方案，采用 Javascript 风格的伪代码，为清楚起见，重命名了几个标识符。

function deleteGreater(head, value) {
    if (head == null) return null;
    if (head.data > value) {
        deallocate(head); //discard the entire list
        return null;
    }

    var current = head;

    while (true) {
        if (current.next == null) return head; //end of list
        if (current.next.data > value) break;
        current = current.next;
    }

    deallocate(current.next); //discard the rest of the list
    current.next = null; 
    return head;
}

我相信您可以将它转换成您想要的任何语言。

对于具有垃圾收集功能的语言，您可以删除 deallocate() 调用。对于没有垃圾回收的语言，覆盖对象的释放方法以确保它也释放 next 属性.

Answer 2

在像 Java 这样有垃圾收集的语言中，将最后一个元素的下一个设置为 null 很简单，在最坏的情况下将是 O(n)（这将与最后一个元素匹配时发生）

Node deleteGreaterThan(Node head, int value){
   if(head==null || head.data>value)return null;//if head is itself greater than value
   Node temp = head;
   while(temp.next != null && temp.next.data<=value){
      temp= temp.next;
   }
   temp.next = null;
   return head;
}

head = deleteGreaterThan(head, 5);

我想在像 c 这样的语言中，您可能必须显式删除每个元素并释放内存，没有使用 c 的经验，所以不能说太多，即使在那种情况下它也只会是 O(n)

Answer 3

就像@100rabh 所说的那样，在没有车库收集的语言中，您需要释放分配的每个节点。这是 C 中如何执行此操作的示例。请注意，调用 Delete 仍然是 O(n)，因为我们实际上在释放当前节点的同时更新了前一个节点的 next 指针。

#include <malloc.h>
#include <stdio.h>

struct _Node {
  struct _Node *next;
  int data;
};

typedef struct _Node Node;

Node* Build(int value)
{
  int i;
  Node *ptr, *head=NULL;

  for (i=1; i<value; i++)
  {
    if(head==NULL)
    {
      head=malloc(sizeof(Node));
      ptr=head;
    }
    else
    {
      ptr->next=malloc(sizeof(Node));
      ptr=ptr->next;
    }
    ptr->data=i;
    ptr->next=NULL;
    printf("Build: node=%p {data=%d next=%p}\n", ptr, ptr->data, ptr->next);
  }
  return head;
}

void Print(Node *head)
{
  Node *ptr=head;
  while(ptr!=NULL)
  {
    printf("Print: node=%p {data=%d, next=%p}\n", ptr, ptr->data, ptr->next);
    ptr=ptr->next;
  }
}

/*
 * We can't pass head or ptr->next directly
 * Because then we can't update it's value when we free what it points to
 * So we pass the pointer to head or ptr->next instead
 * Here we actually update head or ptr->next to point to the next node until we are finished
 */
void Free(Node **ptr)
{
  Node *temp;

  if(ptr==NULL) return;

  while(*ptr!=NULL)
  {
    temp=*ptr;
    *ptr=(*ptr)->next;

    printf("Free: node=%p {data=%d next=%p}\n",temp,temp->data,temp->next);
    temp->data=-temp->data;
    temp->next=NULL;
    free(temp);
  }
}

/*
 * We can't pass head or ptr->next directly
 * Because then we can't update it's value when we free what it points to
 * So we pass the pointer to head or ptr->next instead
 * Nothing gets updated in this function - Free does all the updating
 */
void Delete(Node **ptr, int value)
{
  if(ptr==NULL) return;

  while(*ptr!=NULL)
  {
    if((*ptr)->data>value)
    {
      printf("Delete: node=%p {data=%d node=%p}\n",*ptr,(*ptr)->data,(*ptr)->next);
      Free(ptr);
      return;
    }
    ptr=&(*ptr)->next;
  }
}

int main(void)
{
  Node *head=Build(10);
  Print(head);
  Delete(&head, 5);
  Print(head);
  Free(&head);
  return 0;
}

遇到大于'x'的值时，如何删除链表右侧的所有节点？

How do you delete all the nodes on the right of a linked list when a value greater than 'x' is encountered?

singly-linked-list