二叉查找树&单链表 2016-08-01

[SnackMen]

108. Convert Sorted Array to Binary Search Tree 61. Rotate List

[SnackMen]

/*
*[AC]108. Convert Sorted Array to Binary Search Tree
*/
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums==null || nums.length==0)
            return null;
        int length = nums.length;
        return arrayToBST(0,length-1,nums);
    }
    public TreeNode arrayToBST(int start,int end,int[] nums){
        if(start>end)
            return null;
        int mid = start+(end-start+1)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = arrayToBST(start,mid-1,nums);
        root.right = arrayToBST(mid+1,end,nums);
        return root;
    }
}

[SnackMen]

/*
*[AC]61. Rotate List
*/
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null)
            return null;
        ListNode leftNode=head;
        ListNode rightNode = head;
        ListNode tempNode = head;
        int length=0;
        while(tempNode!=null){
            length++;
            rightNode=tempNode;
            tempNode=tempNode.next;
        }
        k=k%length;
        if(k==0)
            return head;
        tempNode=head;
        k=length-k;
        while(k>0){
            leftNode=tempNode;
            tempNode=tempNode.next;
            k--;
        }
        rightNode.next=head;
        leftNode.next=null;
        return tempNode;
    }
}

[dayang]

/**
 * [AC] LeetCode 108  Convert Sorted Array to Binary Search Tree
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if(nums.length === 0)
        return null;
    function dfs(rt,left,right,flag){
        if(left > right)
            return;
        let mid = (left + right) >>> 1;
        let node = new TreeNode(nums[mid]);
        if(flag === 'left'){
            rt.left = node;
        }else{
            rt.right = node;
        }
        dfs(node,left,mid-1,'left');
        dfs(node,mid+1,right,'right');
    }

    let left = 0,right = nums.length - 1,mid = (left + right) >>> 1;
    let root = new TreeNode(nums[mid]);
    dfs(root,left,mid-1,'left');
    dfs(root,mid+1,right,'right');
    return root;
};

[dayang]

/**
 * [AC] LeetCode 61  Rotate List
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if(head === null)
        return null;
    let p1 = head,p2 = head;
    for(let i = 1; i <= k; i++){
        p2 = p2.next;
        if(p2 === null){
            k = k % i;
            p2 = head;
            while(k--){
                p2 = p2.next;
            }
            break;
        }
    }
    while(p2.next !== null){
        p2 = p2.next;
        p1 = p1.next;
    }
    p2.next = head;
    head = p1.next;
    p1.next = null;
    return head;
};

[wolfogre]

108 . Convert Sorted Array to Binary Search Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    public TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if(start > end)
            return null;
        TreeNode treeNode = new TreeNode(nums[(start + end) / 2]);
        treeNode.left = sortedArrayToBST(nums, start, (start + end) / 2 - 1);
        treeNode.right = sortedArrayToBST(nums, (start + end) / 2 + 1, end);
        return treeNode;
    }
}

[wolfogre]

// [AC] LeetCode 61  Rotate List
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(k == 0)
            return head;

        ListNode fastP = head;
        int length = 0;
        while(k-- > 0 && fastP != null){
            fastP = fastP.next;
            ++length;
        }

        if(fastP == null){
            if(length == 0)
                return null;
            k = (k + 1) % length;
            if(k == 0)
                return head;
            fastP = head;
            while(k-- > 0)
                fastP = fastP.next;
        }

        ListNode p = head;
        while(fastP != null){
            fastP = fastP.next;
            p = p.next;
        }

        ListNode newHead = p, tail = newHead;
        p = head;
        while(tail.next != null)
            tail = tail.next;
        while(p != newHead){
            tail.next = p;
            p = p.next;
            tail = tail.next;
            tail.next = null;
        }

        return newHead;
    }
}

[zhaokuohaha]

108 - C# - 参考题解

public class Solution
{
    public TreeNode SortedArrayToBST(int[] nums)
    {
        if (nums.Length == 0) return null;
        return Insert(nums, 0, nums.Length-1);
    }

    public TreeNode Insert(int [] nums, int low ,int height)
    {
        int mid = (low + height) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        if(low < mid)
            node.left = Insert(nums, low, mid-1);
        if(mid < height)
            node.right = Insert(nums, mid + 1, height);
        return node;
    }
}

[zhaokuohaha]

61 - C# -快慢指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if(head==null || head.next == null || k==0) return head;
        ListNode fast = head;
        ListNode slow = head;
        for(int i=1; i<=k; i++){    //这里从0开始有可能引起除0异常, 故从1开始
            fast = fast.next;
            if(fast == null){
                fast = head;
                k %= i;             //这里可能会得到0
                i = 0;
            }
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }

        fast.next = head;
        fast = slow.next;
        slow.next = null;
        return fast;
    }
}