已超出LinkedList内存限制

”给定一个链表和一个值x，对它进行分区，使得所有小于x的节点在节点大于或等于x之前出现您应该保留两个分区中每个节点的原始相对顺序“。

我的问题是，为什么我们必须有“right.next = null”这一行。为什么它会给出“内存限制超出错误”，如果我不把一个NULL放到LinkedList的末尾？在此先感谢！

public ListNode partition (ListNode head, int x) { 
     if (head==null) return head; 
     ListNode leftDummy = new ListNode(0); 
     ListNode rightDummy = new ListNode(0); 
     ListNode left = leftDummy; 
     ListNode right = rightDummy; 

     while (head!=null) { 
      if (head.val < x) { 
       left.next = head; 
       left = head; 
      } else { 
       right.next = head; 
       right = head; 
      } 
      head = head.next; 
     } 
     // merge the two 
     right.next = null;  // WHY THIS LINE?? 
     left.next = rightDummy.next; 
     return leftDummy.next; 
    }

来源

2016-11-07 Emile

如果没有像你这样分区的原始列表，所以我的猜测是当你合并它们时，你正在创建N^2节点的数量。这是使用调试器可以帮助解释你做得更好的地方。 –

那么，你有两个指针，左右两个，你正在构建分区。它们总是指向相应分区的最后一个元素。 leftDummy和rightDummy是这些分区的开始。那么，你到底应该向左分区的最后一个元素连接到正确的的第一个元素：

left.next = rightDummy.next;

如果用来指向一些其他的元素在原正确的分区的最后一个元素列表中，你应该纠正，否则你可以得到一个无限循环：

right.next = null;

下面是一个例子：

列表：1 - > 5 - > 8 - > 2 将x = 4，在最后你得到两个分区：

leftDummy = 1 -> 2 = left 
rightDummy = 5 -> 8 = right

但是在原始列表中，包含8（现在称为右）的元素指向2，所以如果试图遍历新列表1 - > 2 - > 5 - > 8，实际上会得到：

1 -> 2 -> 5 -> 8 -> 2 -> 5 -> 8 -> 2.....

因此，您必须删除对右侧变量中“next”元素的引用。

来源

2016-11-07 20:36:24 Igor

已超出LinkedList内存限制

回答

相关问题