138. Random pointers list

138_solution2.c

#include "node.h"
#include <stdlib.h>

struct Node *copyRandomList(struct Node *head) {
  if (!head)
    return NULL;

  // pass 1: interleave copies
  for (struct Node *cur = head; cur; cur = cur->next->next) {
    struct Node *copy = malloc(sizeof(struct Node));
    copy->val = cur->val;
    copy->random = NULL;
    copy->next = cur->next;
    cur->next = copy;
  }

  // pass 2: set random pointers
  for (struct Node *cur = head; cur; cur = cur->next->next) {
    if (cur->random)
      cur->next->random = cur->random->next;
  }

  // pass 3: separate the lists
  struct Node *copyHead = head->next;
  for (struct Node *cur = head; cur; cur = cur->next) {
    struct Node *copy = cur->next;
    cur->next = copy->next;
    if (copy->next)
      copy->next = copy->next->next;
  }

  return copyHead;
}

node.h

#pragma once

#include <stddef.h>

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

138_solution1.cpp

#include "node.h"
#include <unordered_map>

using namespace std;

class Solution {
public:
  Node *copyRandomList(Node *head) {
    unordered_map<Node *, Node *> copyOf;
    copyOf[nullptr] = nullptr; // null original -> null copy

    // pass 1: create all copies (no links yet)
    for (Node *cur = head; cur; cur = cur->next)
      copyOf[cur] = new Node(cur->val);

    // pass 2: wire up next and random
    for (Node *cur = head; cur; cur = cur->next) {
      copyOf[cur]->next = copyOf[cur->next];
      copyOf[cur]->random = copyOf[cur->random];
    }

    return copyOf[head];
  }
};

138_solution2.cpp

#include "node.h"
#include <unordered_map>

using namespace std;

class Solution {
public:
  Node *copyRandomList(Node *head) {
    if (!head)
      return nullptr;

    // pass 1: interleave copies
    for (Node *cur = head; cur; cur = cur->next->next) {
      Node *copy = new Node(cur->val);
      copy->next = cur->next;
      cur->next = copy;
    }

    // pass 2: set random pointers
    for (Node *cur = head; cur; cur = cur->next->next) {
      if (cur->random)
        cur->next->random = cur->random->next;
    }

    // pass 3: separate the lists
    Node *copyHead = head->next;
    for (Node *cur = head; cur; cur = cur->next) {
      Node *copy = cur->next;
      cur->next = copy->next;
      if (copy->next)
        copy->next = copy->next->next;
    }

    return copyHead;
  }
};

node.h

#pragma once

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

  Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
};

138_solution1.go

package linkedlists

func copyRandomList(head *Node) *Node {
    copyOf := map[*Node]*Node{nil: nil} // nil original -> nil copy

    // pass 1: create all copies (no links yet)
    for cur := head; cur != nil; cur = cur.Next {
        copyOf[cur] = &Node{Val: cur.Val}
    }

    // pass 2: wire up next and random
    for cur := head; cur != nil; cur = cur.Next {
        copyOf[cur].Next = copyOf[cur.Next]
        copyOf[cur].Random = copyOf[cur.Random]
    }

    return copyOf[head]
}

138_solution2.go

package linkedlists

func copyRandomListInterleaved(head *Node) *Node {
    if head == nil {
        return nil
    }

    // pass 1: interleave copies
    for cur := head; cur != nil; cur = cur.Next.Next {
        cur.Next = &Node{Val: cur.Val, Next: cur.Next}
    }

    // pass 2: set random pointers
    for cur := head; cur != nil; cur = cur.Next.Next {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
    }

    // pass 3: separate the lists
    copyHead := head.Next
    for cur := head; cur != nil; cur = cur.Next {
        copy := cur.Next
        cur.Next = copy.Next
        if copy.Next != nil {
            copy.Next = copy.Next.Next
        }
    }

    return copyHead
}

node.go

package linkedlists

// Definition for a Node.
type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

138_solution1.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> copyOf = new HashMap<>();
        copyOf.put(null, null); // null original -> null copy

        // pass 1: create all copies (no links yet)
        for (Node cur = head; cur != null; cur = cur.next)
            copyOf.put(cur, new Node(cur.val));

        // pass 2: wire up next and random
        for (Node cur = head; cur != null; cur = cur.next) {
            copyOf.get(cur).next = copyOf.get(cur.next);
            copyOf.get(cur).random = copyOf.get(cur.random);
        }

        return copyOf.get(head);
    }
}

138_solution2.java

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null)
            return null;

        // pass 1: interleave copies
        for (Node cur = head; cur != null; cur = cur.next.next) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
        }

        // pass 2: set random pointers
        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null)
                cur.next.random = cur.random.next;
        }

        // pass 3: separate the lists
        Node copyHead = head.next;
        for (Node cur = head; cur != null; cur = cur.next) {
            Node copy = cur.next;
            cur.next = copy.next;
            if (copy.next != null)
                copy.next = copy.next.next;
        }

        return copyHead;
    }
}

Node.java

// 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;
    }
}

138_solution1.js

const Node = require("./node");

var copyRandomList = function (head) {
  const copyOf = new Map([[null, null]]); // null original -> null copy

  // pass 1: create all copies (no links yet)
  for (let cur = head; cur; cur = cur.next) copyOf.set(cur, new Node(cur.val));

  // pass 2: wire up next and random
  for (let cur = head; cur; cur = cur.next) {
    copyOf.get(cur).next = copyOf.get(cur.next);
    copyOf.get(cur).random = copyOf.get(cur.random);
  }

  return copyOf.get(head);
};

138_solution2.js

const Node = require("./node");

var copyRandomList = function (head) {
  if (!head) return null;

  // pass 1: interleave copies
  for (let cur = head; cur; cur = cur.next.next) {
    cur.next = new Node(cur.val, cur.next);
  }

  // pass 2: set random pointers
  for (let cur = head; cur; cur = cur.next.next) {
    if (cur.random) cur.next.random = cur.random.next;
  }

  // pass 3: separate the lists
  const copyHead = head.next;
  for (let cur = head; cur; cur = cur.next) {
    const copy = cur.next;
    cur.next = copy.next;
    if (copy.next) copy.next = copy.next.next;
  }

  return copyHead;
};

node.js

// Definition for a Node.
function Node(val, next, random) {
  this.val = val;
  this.next = next === undefined ? null : next;
  this.random = random === undefined ? null : random;
}

module.exports = Node;

138_solution1.py

from typing import Optional

from node import Node


class Solution:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        copy_of = {None: None}  # None original -> None copy

        # pass 1: create all copies (no links yet)
        cur = head
        while cur:
            copy_of[cur] = Node(cur.val)
            cur = cur.next

        # pass 2: wire up next and random
        cur = head
        while cur:
            copy_of[cur].next = copy_of[cur.next]
            copy_of[cur].random = copy_of[cur.random]
            cur = cur.next

        return copy_of[head]

138_solution2.py

from typing import Optional

from node import Node


class Solution:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return None

        # pass 1: interleave copies
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next

        # pass 2: set random pointers
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # pass 3: separate the lists
        copy_head = head.next
        cur = head
        while cur:
            copy = cur.next
            cur.next = copy.next
            if copy.next:
                copy.next = copy.next.next
            cur = cur.next

        return copy_head

node.py

# Definition for a Node.
class Node:
    def __init__(self, x: int, next: "Node" = None, random: "Node" = None):
        self.val = int(x)
        self.next = next
        self.random = random

138_solution1.rs

use std::collections::HashMap;
use std::rc::Rc;

use crate::node::{Node, NodeRef};

impl Solution {
    pub fn copy_random_list(head: Option<NodeRef>) -> Option<NodeRef> {
        // originals are keyed by address
        let mut copy_of = HashMap::new();

        // pass 1: create all copies (no links yet)
        let mut cur = head.clone();
        while let Some(node) = cur {
            copy_of.insert(Rc::as_ptr(&node), Node::new(node.borrow().val));
            cur = node.borrow().next.clone();
        }

        // None original -> None copy
        let copy = |n: &Option<NodeRef>| n.as_ref().map(|n| copy_of[&Rc::as_ptr(n)].clone());

        // pass 2: wire up next and random
        let mut cur = head.clone();
        while let Some(node) = cur {
            let orig = node.borrow();
            let mut c = copy_of[&Rc::as_ptr(&node)].borrow_mut();
            c.next = copy(&orig.next);
            c.random = copy(&orig.random);
            cur = orig.next.clone();
        }

        copy(&head)
    }
}

138_solution2.rs

use crate::node::{Node, NodeRef};

impl Solution {
    pub fn copy_random_list(head: Option<NodeRef>) -> Option<NodeRef> {
        let head = head?;

        // pass 1: interleave copies
        let mut cur = Some(head.clone());
        while let Some(node) = cur {
            let copy = Node::new(node.borrow().val);
            copy.borrow_mut().next = node.borrow_mut().next.take();
            cur = copy.borrow().next.clone();
            node.borrow_mut().next = Some(copy);
        }

        // pass 2: set random pointers
        let mut cur = Some(head.clone());
        while let Some(node) = cur {
            let orig = node.borrow();
            let copy = orig.next.as_ref().unwrap();
            if let Some(random) = &orig.random {
                copy.borrow_mut().random = random.borrow().next.clone();
            }
            cur = copy.borrow().next.clone();
        }

        // pass 3: separate the lists
        let copy_head = head.borrow().next.clone();
        let mut cur = Some(head);
        while let Some(node) = cur {
            let copy = node.borrow().next.clone().unwrap();
            let next = copy.borrow_mut().next.take();
            if let Some(next) = &next {
                copy.borrow_mut().next = next.borrow().next.clone();
            }
            node.borrow_mut().next = next.clone();
            cur = next;
        }

        copy_head
    }
}

node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a Node.
// LeetCode has no Rust version of this problem; shared ownership is needed
// because several nodes can point at the same node through `random`.
pub type NodeRef = Rc<RefCell<Node>>;

pub struct Node {
    pub val: i32,
    pub next: Option<NodeRef>,
    pub random: Option<NodeRef>,
}

impl Node {
    pub fn new(val: i32) -> NodeRef {
        Rc::new(RefCell::new(Node {
            val,
            next: None,
            random: None,
        }))
    }
}