Блог

Я весь день обрабатывал leetcode, пока что 3 из проблем, с которыми я столкнулся в Eclipse, сработали на 100%, но когда я запускаю их в IDE leetcode, я всегда получаю ошибки нулевого указателя. Вот текущий пример моего кода и проблемы, которую я сейчас решаю: 138. Копировать список со случайным указателем , который просто должен копировать связанный список, но по значению, а не по ссылке.

 /*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

//MY CODE STARTS BELOW ==============================================================
class Solution {
    Node n, r, pointer, output;
    
    public Node copyRandomList(Node head) {
        //Handling weird inputs
        if (head == null){return head;}
        
        Node output = new Node(head.val);
        n = output; r = output;
        pointer = head;
        
        nextHandler();
        randHandler();
        
        return output;
    }
    
    public void nextHandler(){
        if (pointer.next != null){
            n.next = new Node(pointer.next.val);
            n = n.next;
            pointer = pointer.next;
            nextHandler();
        }
    }
    
    
    public  void randHandler(){
        if (pointer.random != null){
            r.random = new Node(pointer.random.val);
            r = r.next;
            pointer = pointer.next;
            randHandler();
        }
    }
}
  

Я предполагаю, что Java не похожа на C / C , не имеет передачи по ссылке, использует передачу по значению. Вероятно, в вашем алгоритме ошибка. Для этого вы можете просто использовать отладчик, даже в LeetCode вы можете просто распечатать все.

Мы бы просто использовали HashMap для решения этой проблемы.

Это пройдет:

 public final class Solution {
    public static final Node copyRandomList(
        final Node head
    ) {
        HashMap<Node, Node> map = new HashMap<>();
        return clone(head, map);
    }

    private static final Node clone(
        final Node head, 
        final HashMap map
    ) {
        if (head == null) {
            return null;
        }

        Node ptr = new Node(head.val);
        map.put(head, ptr);
        ptr.next = clone(head.next, map);
        ptr.random = (Node) map.get(head.random);
        return ptr;
    }
}
  

Вот наиболее эффективное решение LeetCode (которое лучше), O (N) время выполнения, постоянная память:

 /*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
public class Solution {
  public Node copyRandomList(Node head) {

    if (head == null) {
      return null;
    }

    // Creating a new weaved list of original and copied nodes.
    Node ptr = head;
    while (ptr != null) {

      // Cloned node
      Node newNode = new Node(ptr.val);

      // Inserting the cloned node just next to the original node.
      // If A->B->C is the original linked list,
      // Linked list after weaving cloned nodes would be A->A'->B->B'->C->C'
      newNode.next = ptr.next;
      ptr.next = newNode;
      ptr = newNode.next;
    }

    ptr = head;

    // Now link the random pointers of the new nodes created.
    // Iterate the newly created list and use the original nodes' random pointers,
    // to assign references to random pointers for cloned nodes.
    while (ptr != null) {
      ptr.next.random = (ptr.random != null) ? ptr.random.next : null;
      ptr = ptr.next.next;
    }

    // Unweave the linked list to get back the original linked list and the cloned list.
    // i.e. A->A'->B->B'->C->C' would be broken to A->B->C and A'->B'->C'
    Node ptr_old_list = head; // A->B->C
    Node ptr_new_list = head.next; // A'->B'->C'
    Node head_old = head.next;
    while (ptr_old_list != null) {
      ptr_old_list.next = ptr_old_list.next.next;
      ptr_new_list.next = (ptr_new_list.next != null) ? ptr_new_list.next.next : null;
      ptr_old_list = ptr_old_list.next;
      ptr_new_list = ptr_new_list.next;
    }
    return head_old;
  }
}
  

Ссылки

• Для получения дополнительной информации, пожалуйста, обратитесь к Доске обсуждений, где вы можете найти множество хорошо объясненных принятых решений на различных языках, включая алгоритмы низкой сложности и асимптотический анализ времени выполнения / памяти^{1, 2}.