minya
BAN USERa. If you allowed to use extra memory.
1. Convert tree1 and tree2 into sorted arrays by in-order traversal - O(N+M)
2. Merge arrays into one sorted array - O(N+M)
3. Make BST from merged array in a divide-and-conquer manner -O(N+M)
Total - O(M+N)
b. If you must consume a constant memory
Take all elements from first bst and inser into second. It will take O(M log (M+N) ) computaions.
Solution 1: O(n) ops, O(1) memory
public class ListPalindrome {
public boolean isPalindrome(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) {
slow = slow.next;
}
ListNode tail = reverse(slow);
ListNode forward = head;
ListNode backward = tail;
boolean result = true;
while (backward != null){
if (forward.payload != backward.payload) {
result = false;
break;
}
forward = forward.next;
backward = backward.next;
}
// restore list
reverse(tail);
return result;
}
private ListNode reverse(ListNode start) {
ListNode tmp, prev = null;
ListNode run = start;
while (run != null) {
tmp = run;
run = run.next;
tmp.next = prev;
prev = tmp;
}
return prev;
}
public static void main() {
ListNode head = new ListNode(1);
ListNode second = new ListNode(2);
head.next = second;
ListNode third = new ListNode(3);
second.next = third;
ListNode fourth = new ListNode(2);
third.next = fourth;
ListNode fifth = new ListNode(1);
fourth.next = fifth;
System.out.println(new ListPalindrome().isPalindrome(head));
}
}
Solution 2: O(n) ops, O(n) memory, 1 pass
import java.util.Stack;
public class ListPalindrome2 {
public boolean isPalindrome(ListNode head) {
ListNode slow = head;
ListNode fast = head;
Stack<Integer> s = new Stack<Integer>();
while (fast != null && fast.next != null) {
s.push(slow.payload);
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) {
slow = slow.next;
}
while (slow != null){
if (slow.payload != s.pop()) {
return false;
}
slow = slow.next;
}
return true;
}
public static void main() {
ListNode head = new ListNode(1);
ListNode second = new ListNode(2);
head.next = second;
ListNode third = new ListNode(3);
second.next = third;
ListNode fourth = new ListNode(2);
third.next = fourth;
ListNode fifth = new ListNode(1);
fourth.next = fifth;
System.out.println(new ListPalindrome2().isPalindrome(head));
}
}
- minya March 02, 2018