Day 40, 86 Partition List

Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
---------------------------------------------------------------------

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL) return head;
        ListNode *leftHead = NULL, *rightHead = NULL, *end;
        ListNode ** before = &leftHead, **after = &rightHead;
        while (head != NULL) {
            if (head->val >= x) {
                *after = head;
                after = &(head->next);
            }else {
                *before = head;
                before = &(head->next);
            }
            // use end to break the new attached node from the original list
            end = head;
            head = head->next;
            end->next = NULL;
        }
        *before = rightHead; // connect two lists
        return leftHead;
    }
};

Update on Sep-19-2014 
Without double-pointer

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *head1 = NULL, *head2 = NULL,*tail1 = NULL,*tail2 = NULL;
        
        while (head != NULL) {
            if (head->val < x) {
                if (head1 == NULL) {
                    head1 = head;
                    tail1 = head;
                }else {
                    tail1->next = head;
                    tail1 = tail1->next;
                }
            }else {
                
                if (head2 == NULL) {
                    head2 = head;
                    tail2 = head;
                }else {
                    tail2->next = head;
                    tail2 = tail2->next;
                }
            }
            head = head->next;
        }
        
        // merge
        if (tail1 != NULL) tail1->next = head2;
        if (tail2 != NULL) tail2->next = NULL;
        if (head1 == NULL) return head2;
        return head1;
    }
};

Day 39, 79, 82 Word Search, Remove Duplicates from Sorted List II

Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
----------------------------------------------

class Solution {
public:
    bool searchWord (vector<vector<char> > &board, string word, int cur, int row, int col,vector<vector<bool> > &mapping) {
        int rowSize = board.size();
        int colSize = board[0].size();
        if (word.size() == cur) return true; 
        if (word.size() > cur) {
            if (row > 0 && mapping[row-1][col] && word[cur] == board[row-1][col]) {
                mapping[row-1][col] = false;
                if (searchWord(board,word,cur+1,row-1,col,mapping)) {
                    return true;
                }
                mapping[row-1][col] = true;
            }
            if (row < rowSize-1 && mapping[row+1][col] && word[cur] == board[row+1][col]) {
                mapping[row+1][col] = false;
                if (searchWord(board,word,cur+1,row+1,col,mapping)) {
                    return true;
                }
                mapping[row+1][col] = true;
            }
            if (col < colSize-1 && mapping[row][col+1] && word[cur] == board[row][col+1]) {
                mapping[row][col+1] = false;
                if (searchWord(board,word,cur+1,row,col+1,mapping)) {
                    return true;
                }
                mapping[row][col+1] = true;
            }
            if (col > 0 && mapping[row][col-1] && word[cur] == board[row][col-1]) {
                mapping[row][col-1] = false;
                if (searchWord(board,word,cur+1,row,col-1,mapping)) {
                    return true;
                }
                mapping[row][col-1] = true;
            }
        }
        return false;
    }

    bool exist(vector<vector<char> > &board, string word) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rowSize = board.size();
        int colSize = board[0].size();
        vector<vector<bool>> mapping(rowSize, vector<bool>(colSize, true));
        for (int i=0;i<rowSize;i++) {
            for (int j=0;j<colSize;j++) {
                if (board[i][j] == word[0]) {
                    mapping[i][j] = false;
                    if (searchWord(board,word,1,i,j,mapping)) return true;
                    mapping[i][j] = true;
                }
            }
        }
        return false;
    }
};

更新

class Solution {
public:
    bool searchWord(vector<vector<char>>& board, string word,vector<vector<bool>> &visit,int index,int row,int col) {
        if (index == word.length()) return true;
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() 
                || visit[row][col] || word[index] != board[row][col]) {
            return false;
        }
        visit[row][col] = true;
        
        if(searchWord(board,word,visit,index + 1,row + 1,col)
            || searchWord(board,word,visit,index + 1,row - 1,col)
            || searchWord(board,word,visit,index + 1,row,col + 1)
            || searchWord(board,word,visit,index + 1,row,col - 1)) {
            return true;
        }
        visit[row][col] = false;
        return false;
    }


    bool exist(vector<vector<char>>& board, string word) {
        int rowSize = board.size();
        int colSize = board[0].size();
        vector<vector<bool>> mapping(rowSize, vector<bool>(colSize, false));
        for (int i=0; i<rowSize; i++) {
            for (int j=0; j<colSize; j++) {
                if (board[i][j] == word[0]) {
                    if (searchWord(board,word,mapping,0,i,j)) return true;
                }
            }
        }
        return false;
    }
};

BFS理论上可行，但是需要记录太多信息 － 每个点的坐标，当前word的index，和一个额外的（独立的）visit的map。特别是这个map，因为不能backtracking，所有每条path都需要自己独立的map

Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
----------------------------------------------------------------------
Solution #1, iterative

watch out for the tailing number(s)
1,2,2 // cut off
1,2,2,3 // re-attach

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL || head->next == NULL) return head;
        ListNode *ret = NULL, *itr = head->next,*cur = head;
        ListNode **pre = &ret;  // a pointer to a pointer
        while (itr != NULL) {
            if (cur->val != itr->val) {
                if (cur->next == itr) {
                    *pre = cur;
                    pre = &(cur->next);
                    cur = cur->next;
                }else {
                    cur = itr;
                }
            }
            itr = itr->next;
        }
        if (cur->next == NULL) {  // include it if the last one is singular
            *pre = cur;
        }else {  // otherwise, leave out the rest of the list 
            *pre = NULL;
        }
        return ret;
    }
};

Solution #2 from internet, recursive

ListNode *deleteDuplicates(ListNode *head) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    // base case, 0, or 1 item in the list
    if (head == NULL || head->next == NULL) return head;        
    ListNode *ret=NULL;
    ListNode *cur = head;
    int dup=0;

    // remove duplicated values from head
    while (cur->next != NULL && cur->val == cur->next->val)
    {
        ListNode *t=cur;
        cur=cur->next;
        delete(t);
        dup = 1;
    }

    if (!dup)
    {
        ret = cur;
        cur->next = deleteDuplicates(cur->next);            
    }
    else
    {
        ret = deleteDuplicates(cur->next);
    }    
    return ret;        
}

Update on Sep-18-2014
A simpler version of solution #1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode *pre = dummy;
        
        while (head != NULL && head->next != NULL) {
            if (head->val != head->next->val) {
                pre = head;
                head = head->next;
            }else {
                while (head->next != NULL && head->val == head->next->val) {
                    head = head->next;
                }
                pre->next = head->next;
                head = head->next;
            }
            
        }
        
        return dummy->next;
    }
};

Day 38, 77, 78 Combinations, Subsets

Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

--------------------------------------------------------
combination, note that in this case, [1,2] and [2,1] are considered the same
we can use a stack instead of vector for vector<int> num

class Solution {
public:
    void comb (vector<vector<int> >&ret, vector<int> num, vector<int> cur, int k) {
        if (k == 0) {
            ret.push_back(cur);
        }else {
            int size = num.size(); 
            for (int i=0;i<size;i++) {
                vector<int> temp = cur;
                temp.push_back(num[0]);
                num.erase(num.begin());
                comb(ret,num,temp,k-1);
            }
        }
    }

    vector<vector<int> > combine(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> num(n);
        for (int i=0;i<n;i++) {
            num[i] = 1+i;
        }
        vector<int> cur;
        vector<vector<int> > ret;
        comb(ret,num,cur,k);
        return ret;
    }
};

Update on Sep-16-2014

class Solution {
public:
    void comb (vector<vector<int> > &rt, vector<int> cur, int n, int k, int index) {
        if (k == 0) {
            rt.push_back(cur);
            return;
        }
        
        for (int i = index; i <= n + 1 - k; i++) {
            vector<int> temp = cur;
            temp.push_back(i);
            comb(rt,temp,n,k - 1,i + 1);
        }
    }

    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > rt;
        vector<int> v;
        comb(rt,v,n,k,1);
        return rt;
    }
};

同subsets的bit operation的方法

class Solution {
public:
    void helper(vector<vector<int>> &rt,vector<int> cur, int n, int k, int index) {
        if (k == 0) {
            rt.push_back(cur);
            return;
        }
        if (k < 0 || index > n) return;
        
        helper(rt,cur,n,k,index + 1);
        cur.push_back(index);
        helper(rt,cur,n,k - 1,index + 1);
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int> > rt;
        vector<int> cur;
        helper(rt,cur,n,k,1);
        
        return rt;
    }
};

Subsets
Given a set of distinct integers, S, return all possible subsets.
Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

--------------------------------------------------
Solution #1 recursive, Combination

class Solution {
public:
    void sub (vector<vector<int> > &ret, vector<int> S, vector<int> cur) {
        if (S.size() != 0) {
            int size = S.size();
            for (int i=0;i<size;i++) {
                vector<int> temp = cur;
                temp.push_back(S[0]);
                S.erase(S.begin());
                ret.push_back(temp);
                sub(ret,S,temp);
            }
        }
    }

    vector<vector<int> > subsets(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(S.begin(),S.end());
        vector<vector<int> > ret;
        vector<int> cur;
        ret.push_back(cur);
        sub(ret,S,cur);
        return ret;
    }
};

Update on Sep-17-2014

class Solution {
public:
    void sub(vector<vector<int> > &rt, vector<int> cur, vector<int> S, int index) {
        rt.push_back(cur);
        
        for (int i = index; i < S.size(); i++) {
            vector<int> temp = cur;
            temp.push_back(S[i]);
            sub(rt,temp,S,i + 1);
        }
    }

    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(),S.end());
        vector<vector<int> > rt;
        vector<int> v;
        sub(rt,v,S,0);
        
        return rt;
    }
};

Update on Nov-01-2014
Solution #2, Bitmap
For each S it has 2^S.size() subsets and each for loop iteration generates one subset
1 2 3
------
0 0 0
0 0 1
0 1 0
0 1 1
...

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        int numOfSubsets = 1 << S.size();
        sort(S.begin(),S.end());
        vector<vector<int> > rt;
        
        for (int i = 0; i < numOfSubsets; i++) {
            int pos = 0;
            int bitMask = i;
            vector<int> sub;
            
            while (bitMask > 0) {
                if ((bitMask & 1) == 1) {
                    sub.push_back(S[pos]);
                }
                bitMask >>= 1;
                pos++;
            }
            rt.push_back(sub);
        }
        
        return rt;
    }
};

Update on Nov-18-2014
Solution #3 iterative

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > rt;
        vector<int> cur;
        rt.push_back(cur);
        sort(nums.begin(),nums.end());
        
        for (int i = 0; i < nums.size(); i++) {
            vector<vector<int> > temp = rt;
            for (int j = 0; j < temp.size(); j++) {
                temp[j].push_back(nums[i]);
                rt.push_back(temp[j]);
            }
        }
        
        return rt;
    }
};

Update on July-5th-2015
每个数字都可以为 “有” 或 “无”

class Solution {
public:
    void helper(vector<vector<int> > &rt, vector<int> nums, vector<int> cur,int index) {
        if (index == nums.size()) {
            rt.push_back(cur);
            return;
        }
        
        helper(rt,nums,cur,index + 1);
        cur.push_back(nums[index]);
        helper(rt,nums,cur,index + 1);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int> > rt;
        vector<int> cur;
        helper(rt,nums,cur,0);
        
        return rt;
    }
};

ToDo, 以上所有解法要再看一次

Day 37, 74 Search a 2D Matrix

Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.
-------------------------------------------------------------
Do 2 binary searches
Note that start <= end
Searching a 2D Sorted Matrix Part

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       // return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int start = 0, end = m-1;
        if(target< matrix[0][0]) return false;  
        // binary search the first element of each row
        while (start <= end) {
            int mid = (start + end) / 2;
            if (matrix[mid][0] == target) {
                return true;
            }
            if (matrix[mid][0] > target) {
                end = mid - 1;
            }else {
                start = mid + 1;
            }
        }
        // binary search in that particular row
        int row = end;
        start = 0;
        end = n-1;
        while (start <= end) {
            int mid = (start + end) / 2; 
            if (matrix[row][mid] == target) {
                return true;
            }
            if (matrix[row][mid] > target) {
                end = mid - 1;
            }else {
                start = mid + 1;
            }
        }
        return false;
    }
};

Day 36, 71,73 Simplify Path, Set Matrix Zeroes

Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

 -------------------------------------------------
Solution #1, using stack
'/' skip
'.' ignore/continue
'..' pop stack

class Solution {
public:
    string simplifyPath(string path) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i=0;
        stack<string> s;
        while (i < path.length()) {
            while (path[i] == '/' && i < path.length()) { // skip '/'
                 i++;
            }
            if (i == path.length())  break; // if string ends wiht '/'
            int start = i;
            while (path[i] != '/' && i < path.length()) { // get end point of sub path
                i++;
            }
            string elem = path.substr(start,i - start);
            if (elem == ".") {
                continue;
            }
            if (elem == "..") {
                if (!s.empty()) {
                    s.pop();
                }
                continue;
            }
            s.push(elem);
        }
        if (s.empty()) {
            return "/";
        }
        string ret;
        while (!s.empty()) {
            string temp = "/" + s.top();
            ret = temp + ret; 
            s.pop();
        }
        return ret;
    }
};

Solution #2, using two/three pointers
to be continued
  
Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

---------------------------------------
Solution #1, O(m+n) space 

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> row(m,false);
        vector<bool> col(n,false);
        if (m != 1 || n != 1) {
            // find 0
            for (int i=0;i<m;i++) {
                for (int j=0;j<n;j++) {
                    if (matrix[i][j] == 0) {
                        row[i] = true; 
                        col[j] = true;
                    }
                }
            }
            // set to 0
            for (int i=0;i<m;i++) {
                for (int j=0;j<n;j++) {
                    if (row[i] || col[j]) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    }
};

Solution #2, in space
instead of allocating two vectors, using the first row and column to store the zero row/col

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool rowZero = false, colZero = false;
        int rows = matrix.size();
        int cols = matrix[0].size();
        // check first row
        for (int i=0;i<cols;i++) {
            if (matrix[0][i] == 0) {
                rowZero = true;
            }
        }
        // check first column
        for (int i=0;i<rows;i++) {
            if (matrix[i][0] == 0) {
                colZero = true;
            }
        }
        
        for (int i=1;i<rows;i++) {
            for (int j=1;j<cols;j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        for (int i=1;i<rows;i++) {
            for (int j=1;j<cols;j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // if first row has 0
        if (rowZero) {
            for (int i=0;i<cols;i++) {
                matrix[0][i] = 0;
            }
        }
        // if first col has 0
        if (colZero) {
            for (int i=0;i<rows;i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

Day 35, 64 Minimum Path Sum

Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
-------------------------------------------
Solution #1, Memoization
matrix[i][j] = min(matrix[i][j-1],matrix[i-1][j]) + grid[i][j] 

class Solution {
public:
    int minP (vector<vector<int> > &grid, int row, int col,vector<vector<int> > &mapping) {
        if (mapping[row][col] != -1) {
            return mapping[row][col];
        }
        if (row == 0 && col == 0) {
            mapping[row][col] = grid[0][0];
            return mapping[row][col];
        }
        if (row != 0 && col != 0) {
           mapping[row][col] = min(minP(grid,row-1,col,mapping) + grid[row][col],
                                minP(grid,row,col-1,mapping) + grid[row][col]);
            return mapping[row][col];
        }
        if (row == 0) {
            mapping[row][col] = minP(grid,0,col-1,mapping) + grid[0][col];
            return mapping[row][col];
        }
        mapping[row][col] = minP(grid,row-1,0,mapping) + grid[row][0];
        return mapping[row][col];
    }
    
    int minPathSum(vector<vector<int> > &grid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int m = grid.size()-1;
        int n = grid[0].size()-1;
        vector<vector<int> > mapping(m+1);
        for (int i=0;i<m+1;i++) {
            vector<int> v(n+1);
            for (int j=0;j<n+1;j++) {
                v[j] = -1;
            }
            mapping[i] = v;
        }
        return minP(grid,m,n,mapping);
    }
};

Solution #2, DP O(n) space
matrix[i][j] = min(matrix[i][j-1],matrix[i-1][j]) + grid[i][j]

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dp(n+1,INT_MAX);
        dp[1] = 0;
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                dp[j+1] = min(dp[j+1],dp[j]) + grid[i][j];
            }
        }
        return dp[n];
    }
};

因为是minimum，所以dp初始为INT_MAX，如果是maximum，则设为INT_MIN
可先做2d-array的dp，再转化为1d. 注意dp[1] = 0
follow up：增加可以往左
见Google interview questions #2 第5题

Day 34, 59, 61,63 Spiral Matrix II, Rotate List, Unique Paths II

Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.
For example,
Given n = 3,
You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

--------------------------------------
Solution #1 straightforward, follow spiral's track, O(n)

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ret(n);
        if (n == 0) return ret;
        if (n == 1) {
            vector<int> v(1);
            v[0] = 1;
            ret[0] = v;
            return ret;
        }
        for (int i=0;i<n;i++) {
            vector<int> row(n);
            for (int j=0;j<n;j++) {
                row[j] = 0;
            }
            ret[i] = row;
        }
        int row=0,col=0,index=1;  
        while (ret[row][col] == 0) {
            // right
            while (col < n && ret[row][col] == 0) {
                ret[row][col] = index;
                index++;
                col++;
            }
            col--;
            row++;
            // down
            while (row < n && ret[row][col] == 0) {
                ret[row][col] = index;
                index++;
                row++;
            }
            row--;
            col--;
            // left
            while (col >= 0 && ret[row][col] == 0) {
                ret[row][col] = index;
                index++;
                col--;
            }
            col++;
            row--;
            // up
            while (row >= 0 && ret[row][col] == 0) {
                ret[row][col] = index;
                index++;
                row--;
            }
            row++;
            col++;
        }
        return ret;
    }
};

Update on Sep-13-2014
Solution #2
Go google it


Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head == NULL || k == 0) return head;
        ListNode *cur=head, *end=head;
        int count=1;
        while (end->next != NULL) {
            count++;
            end = end->next;
        }
        k = k % count;
        if (k == 0) return head;
        for (int i=0;i<count-k-1;i++) {
            cur = cur->next;
        }
        ListNode *ret = cur->next;
        end->next = head;
        cur->next = NULL;
        return ret;
    }
};

Unique Paths II
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.
Note: m and n will be at most 100.
-----------------------------------
DP, based on unique path I

class Solution {
public:
    int uniquePathsWithObstacles(vector > &obstacleGrid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int matrix[101][101] = {0};
        int m = obstacleGrid.size() - 1;
        int n = obstacleGrid[0].size() - 1;
        matrix[m+1][n] = 1;
        for (int i=m;i>=0;i--) {
            for (int j=n;j>=0;j--) {
                if (obstacleGrid[i][j] == 0) {
                    matrix[i][j] = matrix[i+1][j] + matrix[i][j+1];
                }
            }
        }
        return matrix[0][0];
    }
};

Update on Sep-14-2014
Consider the case when matrix[m + 1][n] or matrix[m][n + 1] has an obstacle

O(n) space

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<int> dp(n + 1,0);
        if (obstacleGrid[m - 1][n - 1] == 1) return 0;
        dp[n - 1] = 1;
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                }else {
                    dp[j] += dp[j + 1];
                }
            }
        }
        return dp[0];
    }
};