Day 42, #92, #109, Reverse Linked List II, Convert Sorted List to Binary Search Tree

Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ? m ? n ? length of list.
----------------------------------------
lets say m = 3, n = 5
1             2              3             4             5            6
|              |                |                             |
head      left           tail                     newHead

/* Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *newHead = NULL, *itr = head,*left = NULL,*tail;
        // move to m-th node
        for (int i = 1; i < m; i++) {
            left = itr;
            itr = itr->next;
        }
        tail = itr;
        // move to n-th node
        for (int i = m; i <= n; i++) {
            ListNode *temp = itr->next;
            itr->next = newHead;
            newHead = itr;
            itr = temp;
        }
        tail->next = itr;
        if (m == 1) {
            return newHead;
        }
        left->next = newHead;
        return head;
    }
};

Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
--------------------------------------------------------------------------
Further reading:
http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
http://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructTree (ListNode *&list,int start, int end) {
        if (start > end) {
            return NULL;
        }
        int mid = start + (end - start) / 2;
        TreeNode *left = constructTree(list,start,mid - 1);
        TreeNode *root = new TreeNode(list->val);
        root->left = left;
        list = list->next;
        root->right = constructTree(list,mid + 1, end);
        return root;
    }


    TreeNode *sortedListToBST(ListNode *head) {
        int n = 0;
        ListNode *itr = head;
        while (itr != NULL ) {
            n++;
            itr = itr->next;
        }
        return constructTree(head,0,n-1);
    }
};

Update Nov-21-2014
Bottom up solution. For each node, build the left child -> root -> right child, follow the in order sequence

Day 41, 91 Decode Ways

Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
------------------------------------------------
similar to steps problem, with some extra conditions
Solution #1 simple recursion

class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.length() == 0 || s[0] == '0') return 0;
        if (s.length() == 1) return 1;
        int fix = 0;
        if (s.length() == 2) {
            fix = 1;
        }
        if (s[0] == '1' || (s[0] == '2' && s[1] < '7')) {
            return numDecodings(s.substr(1)) + numDecodings(s.substr(2)) + fix;
        }
        return numDecodings(s.substr(1));
    }
};

Solution #2 DP

class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.length() == 0 || s[0] == '0') {
            return 0;
        }
        vector<int> ways(s.length() + 1, 1);
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '0') {
                ways[i] = 0;
            }else {
                ways[i] = ways[i+1];
            }
            if (i+1 < s.length() && (s[i] == '1' || (s[i] == '2' && s[i+1] < '7'))) {
                ways[i] += ways[i+2];
            }
        }
        return ways[0];
    }
};

In Java, recursion with memoization

class Solution {
    private Map<String, Integer> map = new HashMap<>();
    public int numDecodings(String s) {
        if (s.length() == 0 || s.charAt(0) == '0') return 0;
        if (s.length() == 1) {
            return 1;
        }
        
        int i = 0;
        String s1 = s.substring(1);
        if (map.containsKey(s1)) {
            i = map.get(s1);
        }else {
            i = numDecodings(s.substring(1)); 
            map.put(s.substring(1), i);
        }
        
        if (s.charAt(0) == '1' || (s.charAt(0) == '2' && s.charAt(1) < '7')) {
            
            String s2 = s.substring(2);
            int j = 0;
            
            if (map.containsKey(s2)) {
                j = map.get(s2);
            }else {
                j = numDecodings(s2); 
                map.put(s2, j);
            }
            
            int rt = 0;
            if (s.length() == 2) rt = 1;
            return i + j + rt;
        }
        
        return i;
    }
}

COME_BACK
写一下O(1) 空间复杂度