LeetCode(2) -- 234, 235, 237

LeetCode Day 2:

P234. Palindrome Linked List (Easy)

一个单向链表，判断它是否是回文。

1 -> 2 false

1 -> 2 -> 2 -> 1 true

我的思路

最简单的办法是先走一趟，看看size是多少，然后中点以前的放进stack里，中点以后的跟它们比较。缺点是一共要走两趟。有没有办法只走一趟解决问题呢？

想到快慢指针。快指针一次走两步，慢指针一次走一步。只要快指针不为空，慢指针就放进stack里。但这样还是相当于走了两趟，并没有省时间。

我的代码

public class E_234_PalindromeLinkedList {
    public boolean isPalindrome(ListNode head) {

        // Count the size
        ListNode pointer = head;
        int size = 0;
        while (pointer != null) {
            size++;
            pointer = pointer.next;
        }

        // Check using stack
        pointer = head;
        Stack<Integer> stack = new Stack<>();
        int counter = 0;
        while (counter < size / 2) {
            stack.push(pointer.val);
            pointer = pointer.next;
            counter++;
        }
        if (size % 2 != 0) {
            pointer = pointer.next;
        }
        while (pointer != null) {
            if (stack.pop() != pointer.val){
                return false;
            }
            pointer = pointer.next;
        }
        return true;
    }
}

超过37.2%，比较慢。

最优解：

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head, prev = null, tmp = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            tmp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = tmp;
        }

        if (fast != null) slow = slow.next;
        while (slow != null) {
            if (prev.val != slow.val) return false;
            prev = prev.next;
            slow = slow.next;
        }

        return true;
    }
}

好后悔刚刚没用快慢指针实现-.-

不过人家并没有用stack, 而是把前半段的指针全部调转方向。比如：

1 -> 2 -> 3 -> 3 -> 2 -> 1  变成：

1 <- 2 <- 3    3 -> 2 -> 1

这样再比较两个Linked List。非常聪明。

所以Linked List调转方向也是一个非常重要的方法，要熟练掌握通过三个指针把Linked List调头的算法。

比如有三个节点1 -> 2 -> 3

1. 先把临时指针移动到2。
2. 把当前指针的方向调头，指向前一个。
3. 因为前一个已经有人指着了，就不必保存了，所以把前一个指针移动到当前位置。
4. 当前位置用刚才的前一个指针保存了，所以当前位置那个指针也完成任务了，移动到下一个位置，也就是刚才用temp暂存的节点。

P235. Lowest Common Ancestor of a Binary Search Tree (Easy)

一个二叉搜索树，任意给两个节点，问它们的共同祖先。（最低的那个）

我的思路：

因为是二叉搜索树，两个节点的共同祖先必然是两个数之间的一个数。所以只要从根节点向下遍历，只要发现某个数的大小位于这两个节点数之间，那一定是它们的共同祖先。

我的代码：

public class E_235_LCAofBST {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }

        // 因为不知道p和q谁大谁小，需要确定大小关系
        int low, high;
        if (p.val < q.val) {
            low = p.val;
            high = q.val;
        } else if (p.val > q.val){
            low = q.val;
            high = p.val;
        } else {
            return p;
        }

        // 遍历树，从上往下找第一个两数之间的数。
        return help(root, low, high);

    }

    private TreeNode help(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val >= low && root.val <= high) {
            return root;
        } else {
            TreeNode left = help(root.left, low, high);
            if (left != null) {
                return left;
            }
            TreeNode right = help(root.right, low, high);
            if (right != null) {
                return right;
            }
        }
        return null;
    }
}

超过21%，非常慢。

答案：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // Value of current node or parent node.
        int parentVal = root.val;

        // Value of p
        int pVal = p.val;

        // Value of q;
        int qVal = q.val;

        if (pVal > parentVal && qVal > parentVal) {
            // If both p and q are greater than parent
            return lowestCommonAncestor(root.right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            // If both p and q are lesser than parent
            return lowestCommonAncestor(root.left, p, q);
        } else {
            // We have found the split point, i.e. the LCA node.
            return root;
        }
    }
}

因为p,q是树里的节点，所以父节点跟它们是一定存在大小关系的。我之前判断非空的很多步骤都是多余的。

一定会存在一个结果的，所以不需要返回null。

只要根据范围，向左或向右持续查找，肯定能找到。找到了就返回这个节点。

P237. Delete Node in a Linked List (Easy)

删除linked list里的一个节点。

我的思路：

这个题很奇怪，没给head。没思路。。。

答案：

class Solution {
   public void deleteNode(ListNode n) {
       if (n == null || n.next == null) {
           return;
       }
       n.val = n.next.val;
       n.next = n.next.next;
   }
}

因为没有当前节点的引用，无法只调指针。因为当前节点要删除，所以它的值也没用了，就用下一个节点的值覆盖当前节点为的值。然后把下一个节点删除即可。