Month: September 2018

This method doesn’t use a HashMap.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
 public RandomListNode copyRandomList(RandomListNode head) {
  if (head == null)
   return null;
  // Step 1 - Store copy in next
  RandomListNode n = head;
  while (n != null) {
   RandomListNode c = new RandomListNode(n.label);
   c.next = n.next;
   n.next = c;
   n = c.next;
  }
  // Step 2 - Copy Random reference
  n = head;
  while (n != null) {
   if (n.random != null) {
    n.next.random = n.random.next;
   }
   n = n.next.next;
  }
  // Step 3 - Break references
  n = head;
  RandomListNode ret = head.next;
  while (n != null) {
   RandomListNode copy = n.next;
   n.next = copy.next;
   if (n.next != null) {
    copy.next = n.next.next;
   }
   n = n.next;
  }
  return ret;
 }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public void flatten(TreeNode root) {
  moveLeftToRight(root);
 }

 public TreeNode moveLeftToRight(TreeNode root) {
  if (root == null)
   return null;
  TreeNode last = null;
  TreeNode right = root.right;
  if (root.left != null) {
   root.right = root.left;
   root.left = null;
   last = moveLeftToRight(root.right);
   last.right = right;
  }
  if (right != null) {
   last = moveLeftToRight(right);
  }
  return (last != null ? last : root);
 }
}