<repo_name>hanwaer/leetcode_in_C<file_sep>/src/101_SymmetricTree.c
/*
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / \
  2   2
   \   \
   3    3
Note:
Bonus points if you could solve it both recursively and iteratively.
*/

bool helper(struct TreeNode *left, struct TreeNode *right) {
    if (!left || !right) 
        return left==right;

    if (left->val != right->val)
        return false;

    return helper(left->left, right->right) && helper(left->right, right->left);
}

bool isSymmetric(struct TreeNode *root) {
    if (!root)
        return true;

    return helper(root->left, root->right);
}
<file_sep>/src/014_LongestCommonPrefix.c
/*
 * Write a function to find the longest common prefix string amongst an 
 * array of strings.
 */

char* longestCommonPrefix(char **strs, int strsSize) {
    if (strsSize == 0)
        return "";

    int i, j, max_len = strlen(strs[0]), len;
    char *res = strdup(strs[0]);
    for (i = 0; i < max_len; i++) {
        for (j = 1; j < strsSize; j++) {
            if (strs[j - 1][i] != strs[j][i])
                break;
        }
        if (j != strsSize) {
            res[i] = 0;
            return res;
        }
    }
    return res;
}
<file_sep>/src/292_NimGame.c
/*
 * You are playing the following Nim Game with your friend: There is a heap
 * of stones on the table, each time one of you take turns to remove 1 to 3
 * stones. The one who removes the last stone will be the winner. You will
 * take the first turn to remove the stones.
 *
 * Both of you are very clever and have optimal strategies for the game.
 * Write a function to determine whether you can win the game given the
 * number of stones in the heap.
 *
 * For example, if there are 4 stones in the heap, then you will never win
 * the game: no matter 1, 2, or 3 stones you remove, the last stone will
 * always be removed by your friend.
 */

bool canWinNim(int n) {
    return !(n % 4 == 0);
}
<file_sep>/src/104_MaximumDepthOfBinaryTree.c
/*
 * Given a binary tree, find its maximum depth.
 *
 * The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
 */

int maxDepth(struct TreeNode *root) {
    int left, right;

    if (!root)
        return 0;

    if (!root->left && !root->right)
        return 1;

    left = right = 1;
    if (root->left) 
        left += maxDepth(root->left);

    if (root->right)
        right += maxDepth(root->right);

    return left>right?left:right;
}
<file_sep>/src/165_CompareVersionNumbers.c
/*
 * Compare two version numbers version1 and version2.
 * If version1 > version2 return 1, if version1 < version2 return -1,
 * otherwise return 0.
 *
 * You may assume that the version strings are non-empty and contain only
 * digits and the . character.
 * The . character does not represent a decimal point and is used to
 * separate number sequences.
 * For instance, 2.5 is not "two and a half" or "half way to version three",
 * it is the fifth second-level revision of the second first-level revision.
 *
 * Here is an example of version numbers ordering:
 *
 * 0.1 < 1.1 < 1.2 < 13.37
 */

int compareVersion(char *version1, char *version2) {
    int ret = 0, c1, c2, i, max;
    int *r1, *r2;
    char *n1 = NULL, *n2 = NULL, *p1 = version1, *p2 = version2;

    c1 = c2 = 1;
    while (n1 = strchr(p1, '.')) {c1++; p1 = n1 + 1;}
    while (n2 = strchr(p2, '.')) {c2++; p2 = n2 + 1;}

    max = c1 > c2 ? c1 : c2;
    r1 = calloc(max, sizeof(int));
    r2 = calloc(max, sizeof(int));

    c1 = c2 = 0;
    p1 = version1;
    p2 = version2;

    for (n1 = strsep(&p1, "."); n1; n1 = strsep(&p1, ".")) {
        r1[c1++] = atoi(n1);
    }


    for (n2 = strsep(&p2, "."); n2; n2 = strsep(&p2, ".")) {
        r2[c2++] = atoi(n2);
    }

    for (i = 0; i < c1 || i < c2; i++) {
        if (r1[i] > r2[i]) {
            ret = 1;
            break;
        } else if (r1[i] < r2[i]) {
            ret = -1;
            break;
        }
    }

    free(r1);
    free(r2);
    return ret;
}
<file_sep>/src/023_MergeKSortedLists.c
/*
 * Merge k sorted linked lists and return it as one sorted list. Analyze and
 * describe its complexity.
 */

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode *merge2lists(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode dummy = {0};
    struct ListNode *p = &dummy;
    
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            p->next = l1;
            l1 = l1->next;
        } else {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    if (l1 != NULL) p->next = l1;
    if (l2 != NULL) p->next = l2;
    return dummy.next;
}

struct ListNode* mergeKLists(struct ListNode **lists, int listsSize) {
    int begin, end;
    if (lists == NULL || listsSize == 0)
        return NULL;
        
    end = listsSize - 1;
    while (end > 0) {
        begin = 0;
        while (begin < end) {
            lists[begin] = merge2lists(lists[begin], lists[end]);
            begin++;
            end--;
        }
    }
    return lists[0];
}
<file_sep>/src/198_HouseRobber.c
/*
 * You are a professional robber planning to rob houses along a street.
 * Each house has a certain amount of money stashed, the only constraint
 * stopping you from robbing each of them is that adjacent houses have
 * security system connected and it will automatically contact the police
 * if two adjacent houses were broken into on the same night.
 *
 * Given a list of non-negative integers representing the amount of money
 * of each house, determine the maximum amount of money you can rob tonight
 * without alerting the police.
 */

#define max(a,b) (a) > (b) ? (a) : (b)
int rob(int *nums, int numsSize) {
    int i, a = 0, b = 0;

    for (i = 0; i < numsSize; i++) {
        if (i % 2 == 0)
            a = max(a + nums[i], b);
        else
            b = max(a, b + nums[i]);
    }

    return max(a,b);
}
<file_sep>/src/003_LongestSubstringWithoutRepeatingCharacters.c
/*
 * Given a string, find the length of the longest substring without repeating characters.
 *
 * Examples:
 * Given "abcabcbb", the answer is "abc", which the length is 3.
 * Given "bbbbb", the answer is "b", with the length of 1.
 * Given "pwwkew", the answer is "wke", with the length of 3. 
 * Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
 */

int lengthOfLongestSubstring(char *s) {
    char *l, *r;
    int max = 0;
    char *map[256] = {0};

    for (l=r=s; *r; r++) {
        if (map[*r] != NULL) {
            l = l>map[*r]?l:map[*r]+1;
        }
        max = max>(r-l+1)?max:(r-l+1);
        map[*r] = r;
    }

    return max;
}
<file_sep>/src/647_PalindromicSubstrings.c
/*
 * Given a string, your task is to count how many palindromic substrings
 * in this string.
 *
 * The substrings with different start indexes or end indexes are counted
 * as different substrings even they consist of same characters.
 *
 * Example 1:
 * Input: "abc"
 * Output: 3
 * Explanation: Three palindromic strings: "a", "b", "c".
 *
 * Example 2:
 * Input: "aaa"
 * Output: 6
 * Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
 *
 * Note:
 * The input string length won't exceed 1000.
 */

int countSubstrings(char *s) {
    int i, cnt = 0;

    for (i = 0; s[i]; i++) {
        cnt += countPalindromic(s, i, i);
        cnt += countPalindromic(s, i, i+1);
    }

    return cnt;
}

int countPalindromic(char *s, int lf, int rt) {
    int cnt = 0;
    while ((lf>=0) && s[rt] && s[lf--] == s[rt++]) {
        cnt++;
    }
    return cnt;
}

<file_sep>/src/208_ImplementTrie.c
/*
 * Implement a trie with insert, search, and startsWith methods.
 *
 * Note:
 * You may assume that all inputs are consist of lowercase letters a-z.
 */

struct TrieNode {
    bool w;
    struct TrieNode *childs[26];
};

/** Initialize your data structure here. */
struct TrieNode* trieCreate() {
    struct TrieNode *t;

    t = malloc(sizeof(struct TrieNode));
    if (!t) return NULL;

    t->w = false;
    int i;
    for (i = 0; i < 26; i++) {
        t->childs[i] = NULL;
    }
    return t;
}

/** Inserts a word into the trie. */
void insert(struct TrieNode *root, char *word) {
    int i;
    struct TrieNode *p = root;

    for (i = 0; i < strlen(word); i++) {
        if (p->childs[word[i]-'a'] == NULL) {
            p->childs[word[i]-'a'] = trieCreate();
        }
        p = p->childs[word[i]-'a'];
    }
    p->w = true;
}

/** Returns if the word is in the trie. */
bool search(struct TrieNode *root, char *word) {
    int i;
    struct TrieNode *p = root;

    for (i = 0; i < strlen(word); i++) {
        if (p->childs[word[i]-'a'] == NULL)
            return false;
        p = p->childs[word[i]-'a'];
    }
    return p->w;
}

/** Returns if there is any word in the trie 
    that starts with the given prefix. */
bool startsWith(struct TrieNode* root, char* prefix) {
    int i;
    struct TrieNode *p = root;

    for (i = 0; i < strlen(prefix); i++) {
        if (p->childs[prefix[i]-'a'] == NULL)
            return false;
        p = p->childs[prefix[i]-'a'];
    }

    return true;
}

/** Deallocates memory previously allocated for the TrieNode. */
void trieFree(struct TrieNode* root) {
    int i;

    for (i = 0; i < 26; i++) {
        if (root->childs[i] != NULL) {
            trieFree(root->childs[i]);
            free(root->childs[i]);
        }
    }
}

// Your Trie object will be instantiated and called as such:
// struct TrieNode* node = trieCreate();
// insert(node, "somestring");
// search(node, "key");
// trieFree(node);
<file_sep>/src/083_RemoveDuplicatesFromSortedList.c
/*
 * Given a sorted linked list, delete all duplicates such that each element appear only once.
 *
 * For example,
 * Given 1->1->2, return 1->2.
 * Given 1->1->2->3->3, return 1->2->3.
 */

struct ListNode* deleteDuplicates(struct ListNode *head) {
    if (!head)
        return NULL;

    struct ListNode *p = head, *n = head->next;

    while (n) {
        if (p->val == n->val) {
            p->next = n->next;
            n = n->next;
        } else {
            p = n;
            n = n->next;
        }
    }

    return head;
}
<file_sep>/README.md
# leetcode in C
Leetcode solutions in C programming language

## Introduction:
My submissions of leetcode.com online judge system, all solutions accepted.

* include: simple implementations of some common data structure, like hash table, list, heap, etc... they are intentionally kept stupid to allow me write it in interview timeframe.

* src: all the code with the question description.


<file_sep>/src/153_FindMinimumInRotatedSortedArray.c
/*
 * Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
 *
 * (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 *
 * Find the minimum element.
 *
 * You may assume no duplicate exists in the array.
 */


int findMin(int *nums, int numsSize) {
    int i, min;

    min = nums[0];
    for (i = 1; i < numsSize; i++) {
        if (min > nums[i])
            return nums[i];
    }

    return min;
}
<file_sep>/src/268_MissingNumber.c
/*
 * Given an array containing n distinct numbers taken from 0, 1, 2, ..., n,
 * find the one that is missing from the array.
 *
 * Example 1:
 * Input: [3,0,1]
 * Output: 2
 *
 * Example 2:
 * Input: [9,6,4,2,3,5,7,0,1]
 * Output: 8
 *
 * Note:
 * Your algorithm should run in linear runtime complexity. Could you
 * implement it using only constant extra space complexity?
 */

int missingNumber(int *nums, int numsSize) {
    int i, tmp, max, missing = -1;

    for (i = 0; i < numsSize; i++) {
        while (nums[i] != i) {
            tmp = nums[i];
            if (nums[i] >= numsSize) {
                max = nums[i];
                missing = i;
                break;
            } else if (missing == nums[i]) {
                nums[missing] = missing;
                missing = i;
                break;
            } else {
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
        }
    }

    if (missing == -1)
        return numsSize;
    return missing;
}
<file_sep>/include/int_hash.h
#ifndef __INT_HASH_H_
#define __INT_HAHS_H_

#define ROOM 1024

struct kv {
    int key; 
    int value;
};

struct bucket {
    int len;
    int cap;
    struct int_kv *items;
};

struct bucket map[ROOM];
void hinit() {
    memset(map, 0, sizeof(struct bucket) * ROOM);    
}

int hash(int key) {
    return (unsigned int)key % ROOM;
}

int hget(int key, int *value) {
    int idx = hash(key);
    int i;
    for (i = 0; i < map[idx].len; i++) {
        if (map[idx].items[i].key == key) {
            *value = map[idx].items[i].value;
            return 0;
        }
    }
    return -1; 
}

void hset(int key, int value) {
    int idx = hash(key);
    int i; 
    if (map[idx].len == 0) {
        map[idx].cap = 32;
        map[idx].items = malloc(32 * sizeof(struct kv));
    } else {
        for (i = 0; i < map[idx].len; i++) {
            if (map[idx].items[i].key == key) {
                map[idx].items[i].value = value;
                return;
            }
        }
        if (map[idx].len + 1 > map[idx].cap) {
            map[idx].cap += 32;
            map[idx].items = realloc(map[idx].items, (map[idx].cap + 32) * sizeof(struct kv));    
        }

    }

    map[idx].items[map[idx].len].key = key;
    map[idx].items[map[idx].len++].value = value;
}

#endif

<file_sep>/src/202_HappyNumber.c
/*
 * Write an algorithm to determine if a number is "happy".
 *
 * A happy number is a number defined by the following process: Starting
 * with any positive integer, replace the number by the sum of the squares
 * of its digits, and repeat the process until the number equals 1 (where
 * it will stay), or it loops endlessly in a cycle which does not include 1.
 * Those numbers for which this process ends in 1 are happy numbers.
 *
 * Example: 19 is a happy number
 *
 * 1^2 + 9^2 = 82
 * 8^2 + 2^2 = 68
 * 6^2 + 8^2 = 100
 * 1^2 + 0^2 + 0^2 = 1
 */

bool isHappy(int n) {
    int cal(int n) {
        int x = 0, y = n;
        while (y) {
            x += (y % 10) * (y % 10);
            y = y/10;
        }
        return x;
    }

    int slow = cal(n);
    int fast = cal(slow);
    while (fast != slow) {
        slow = cal(slow);
        fast = cal(fast);
        fast = cal(fast);
    }

    return slow==1; 
}
<file_sep>/src/070_ClimbingStairs.c
/*
 * You are climbing a stair case. It takes n steps to reach to the top.
 *
 * Each time you can either climb 1 or 2 steps. In how many distinct
 * ways can you climb to the top?
 *
 * Note: Given n will be a positive integer.
 *
 * Example 1:
 * Input: 2
 * Output:  2
 * Explanation:  There are two ways to climb to the top.
 *
 * 1. 1 step + 1 step
 * 2. 2 steps
 * Example 2:
 *
 * Input: 3
 * Output:  3
 * Explanation:  There are three ways to climb to the top.
 *
 * 1. 1 step + 1 step + 1 step
 * 2. 1 step + 2 steps
 * 3. 2 steps + 1 step
 */

int climbStairs(int n) {
    int n1 = 2, n2 = 1, all = 0;

    if (n < 3)
        return n;

    for (int i = 3; i<=n; i++) {
        all = n1 + n2;
        n2 = n1;
        n1 = all;
    }
    return all;
}
<file_sep>/src/141_LinkedListCycle.c
/*
 * Given a linked list, determine if it has a cycle in it.
 *
 * Follow up:
 * Can you solve it without using extra space?
 */

bool hasCycle(struct ListNode *head) {
    struct ListNode *p1, *p2;
    p1 = p2 = head;
    while (p1 && p2) {
        p1 = p1->next;
        p2 = p2->next;
        if (!p2)
            break;
        p2 = p2->next;
        if (p2 && (p1 == p2))
            return true;
    }
    return false;
}<file_sep>/src/056_MergeIntervals.c
/*
 * Given a collection of intervals, merge all overlapping intervals.
 *
 * For example,
 * Given [1,3],[2,6],[8,10],[15,18],
 * return [1,6],[8,10],[15,18].
 */

int cmp(void *a, void *b) {
    return ((struct Interval *)a)->start - ((struct Interval *)b)->start;
}


/*
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct Interval* merge(struct Interval *intervals, int intervalsSize, int *returnSize) {
    qsort(intervals, intervalsSize, sizeof(struct Interval), cmp);
    int i, j, k, min_start, max_end;
    struct Interval* result = calloc(intervalsSize, sizeof(struct Interval));

    k = 0;
    for (i = 0; i < intervalsSize; ) {
        min_start = intervals[i].start;
        max_end = intervals[i].end;
        for (j = i + 1; j < intervalsSize; j++) {
            if (max_end >= intervals[j].start)
                max_end = max_end > intervals[j].end ? max_end : intervals[j].end;
            else
                break;
        }

        i = j;
        result[k].start = min_start;
        result[k].end = max_end;
        k++;
    }

    *returnSize = k;
    return result;
}
<file_sep>/src/283_MoveZeroes.c
/*
 * Given an array nums, write a function to move all 0's to the end of it
 * while maintaining the relative order of the non-zero elements.
 *
 * For example, given nums = [0, 1, 0, 3, 12], after calling your function,
 * nums should be [1, 3, 12, 0, 0].
 *
 * Note:
 * You must do this in-place without making a copy of the array.
 * Minimize the total number of operations.
 */


void moveZeroes(int *nums, int numsSize) {
    int n, i;
    for (i = 0; i < numsSize; i++) {
        if (nums[i] && n++ != i) {
            nums[n-1] = nums[i];
            nums[i] = 0;
        }
    }
}
<file_sep>/src/171_ExcelSheetColumnNumber.c
/*
Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
*/

int titleToNumber(char *s) {
    int sum = 0;
    while (*s != '\0') {
        sum = sum * 26 + *s - 'A' + 1;
        s++;
    }

    return sum;
}
<file_sep>/src/053_MaximumSubarray.c
/*
 * Find the contiguous subarray within an array (containing at least one
 * number) which has the largest sum.
 *
 * For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
 * the contiguous subarray [4,-1,2,1] has the largest sum = 6.
 */

int maxSubArray(int *nums, int numsSize) {
    int max, tmp_max, i;

    if (!nums)
        return -1-0x7fffffff;

    max = nums[0];
    tmp_max = nums[0];
    for (i = 1; i < numsSize; i++) {
        tmp_max = (tmp_max + nums[i]) > nums[i] ? (tmp_max + nums[i]) : nums[i];
        max = max > tmp_max ? max : tmp_max;
    }

    return max;
}
<file_sep>/src/169_MajorityElement.c
/*
 * Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
 *
 * You may assume that the array is non-empty and the majority element always exist in the array.
 */

int majorityElement(int* nums, int numsSize) {
    int m, n, i;
    m = nums[0];
    n = 0;
    for (i = 0; i < numsSize; i++){
        if (n == 0)
            m = nums[i];
        if (m == nums[i])
            n++;
        else
            n--;
    }

    return m;
}
<file_sep>/src/206_ReverseLinkedList.c
/*
 * Reverse a singly linked list.
 */

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode *head) {
    struct ListNode *p, *x, *y;

    if (!head)
        return NULL;

    x = head;
    p = NULL;
    y = head->next;

    while (y) {
        x->next = p;
        p = x;
        x = y;
        y = y->next;
    }
    x->next = p;

    return x;
}
<file_sep>/src/024_SwapNodesInPairs.c
/*
 * Given a linked list, swap every two adjacent nodes and return its head.
 * 
 * For example,
 * Given 1->2->3->4, you should return the list as 2->1->4->3.
 * Your algorithm should use only constant space. You may not modify the
 * values in the list, only nodes itself can be changed.
 */

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode *head) {
    struct ListNode *new_head = NULL;
    struct ListNode *p1 = head, *p2 = NULL, *temp = NULL;
    struct ListNode *last = NULL;

    if (!head) 
        return NULL;
    if (!head->next)
        return head;

    new_head = head->next;    
    for (; p1 && (p2 = p1->next); p1 = p1->next) {
        if (last)
            last->next = p2;
        temp = p2->next;
        p2->next = p1;
        p1->next = temp;
        last = p1;
    }

    return new_head;
}
<file_sep>/src/050_Pow.c
/*
 * Implement pow(x, n).
 *
 *
 * Example 1:
 *
 * Input: 2.00000, 10
 * Output: 1024.00000
 * Example 2:
 *
 * Input: 2.10000, 3
 * Output: 9.26100
 */

double myPow(double x, int n) {
    if (n == 0) 
        return 1;

    double d = myPow(x, n / 2);
    if (n % 2)
        return (n % 2 < 0) ? (1 / x * d * d) : (x * d * d);
    return d * d;
}
<file_sep>/src/028_ImplementStrStr.c
/*
 * Implement strStr().
 * Return the index of the first occurrence of needle in haystack, or -1 if
 * needle is not part of haystack.
 *
 * Example 1:
 * Input: haystack = "hello", needle = "ll"
 * Output: 2
 *
 * Example 2:
 * Input: haystack = "aaaaa", needle = "bba"
 * Output: -1
 */

int strStr(char *haystack, char *needle) {
    int i, j;
    int len_haystack = strlen(haystack);
    int len_needle = strlen(needle);
    if (len_needle == 0)
        return 0;

    for (i = 0; i <= len_haystack - len_needle; i++) {
        for (j = 0; j < len_needle; j++) {
            if (haystack[i + j] != needle[j])
                break;
        }
        if (j == len_needle)
            return i;
    }
    return -1;
}
<file_sep>/src/242_ValidAnagram.c
/*
 * Given two strings s and t, write a function to determine if t is an
 * anagram of s.
 *
 * For example,
 * s = "anagram", t = "nagaram", return true.
 * s = "rat", t = "car", return false.
 *
 * Note:
 * You may assume the string contains only lowercase alphabets.
 *
 * Follow up:
 * What if the inputs contain unicode characters? How would you adapt your
 * solution to such case?
 */

bool isAnagram(char* s, char* t) {
    if (!s && !t) return true;
    if (!s || !t) return false;

    if (strlen(s) != strlen(t)) return false;

    int res[26] = {0};
    int i;

    for (i=0; i<strlen(s); i++) {res[s[i]-'a']++;}
    for (i=0; i<strlen(t); i++) {res[t[i]-'a']--;}

    for (i=0; i<26; i++) {
        if (res[i]!=0)
            return false;
    }
    return true;
}
<file_sep>/src/160_IntersectionOfTwoLinkedLists.c
/*
Write a program to find the node at which the intersection of two singly linked lists begins.


For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.


Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
*/

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
	int na = 0, nb = 0, i;
    struct ListNode *ta, *tb;

    for (na = 0, ta = headA; ta; ta = ta->next)
        na++;

    for (nb = 0, tb = headB; tb; tb = tb->next)
        nb++;

    ta = headA;
    tb = headB;
    if (na > nb) {
        for (i = 0; i < na - nb; i++)
            ta = ta->next;
    } else {
        for (i = 0; i < nb - na; i++)
            tb = tb->next;
    }

    while (ta && tb) {
        if (ta == tb)
            return ta;
        ta = ta->next;
        tb = tb->next;
    }
    return NULL;
}
<file_sep>/src/002_AddTwoNumbers.c
/*
 * You are given two non-empty linked lists representing two non-negative
 * integers. The digits are stored in reverse order and each of their nodes
 * contain a single digit. Add the two numbers and return it as a linked list.
 * 
 * You may assume the two numbers do not contain any leading zero, except
 * the number 0 itself.
 * 
 * Example
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 */ 

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode head;
    struct ListNode *n = &head;
    int extra = 0;

    while (l1 || l2 || extra) {
        struct ListNode *node = calloc(1, sizeof(struct ListNode));
        node->val = ((l1?l1->val:0) + (l2?l2->val:0) + extra) % 10;
        extra = ((l1?l1->val:0) + (l2?l2->val:0) + extra) / 10;
        l1 = l1?l1->next:NULL;
        l2 = l2?l2->next:NULL;
        n->next = node;
        n = n->next;
    }

    return head.next;
}
<file_sep>/src/617_MergeTwoBinaryTrees.c
/*
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \
        3   2                     1   3                        
       /                           \   \
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \
	 5   4   7
Note: The merging process must start from the root nodes of both trees.
*/

struct TreeNode* mergeTrees(struct TreeNode *t1, struct TreeNode *t2) {
    struct TreeNode *root;
    if (!t1 && !t2)
        return NULL;

    root = malloc(sizeof(struct TreeNode));
    root->val = (t1?t1->val:0) + (t2?t2->val:0);
    root->left = mergeTrees(t1?t1->left:NULL, t2?t2->left:NULL);
    root->right = mergeTrees(t1?t1->right:NULL, t2?t2->right:NULL);

    return root;
}
<file_sep>/src/118_PascalsTriangle.c
/*
Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
*/

int** generate(int numRows, int **columnSizes) {
    int i, j;
    int **rr = calloc(numRows, sizeof(int*));
    int *s = calloc(numRows, sizeof(int));

    for (i = 0; i < numRows; i++) {
        s[i] = i + 1;
        rr[i] = calloc(i + 1, sizeof(int));
        for (j = 0; j <= i; j++) {
            if (j == 0 || j == i)
                rr[i][j] = 1;
            else
                rr[i][j] = rr[i-1][j-1] + rr[i-1][j];
        }    
    }

    *columnSizes = s;
    return rr;
}
<file_sep>/src/013_RomanToInteger.c
/*
 * Given a roman numeral, convert it to an integer.
 * Input is guaranteed to be within the range from 1 to 3999.
 */

int romanToInt(char* s) {
    if (!s)
        return 0;

    int i, len, sum = 0;
    int m[26] = {[2]=100,[3]=500,[8]=1,[11]=50,[12]=1000,[21]=5,[23]=10};
    len = strlen(s);

    sum = m[s[len - 1] - 'A'];
    for (i = len - 2; i >= 0; i--) {
        sum += (m[s[i] - 'A'] >= m[s[i + 1] - 'A']) ? m[s[i] - 'A'] : -m[s[i] - 'A'];
    } 

    return sum;
}
<file_sep>/src/217_ContainsDuplicate.c
/*
 * Given an array of integers, find if the array contains any duplicates.
 * Your function should return true if any value appears at least twice in
 * the array, and it should return false if every element is distinct.
 */

bool containsDuplicate(int *nums, int numsSize) {
    int i,j;

    for (i = 0; i < numsSize - 1; i++) {
        for (j = i+1; j<numsSize; j++) {
            if (nums[i] == nums[j])
                return true;
        }
    }

    return false;
}
<file_sep>/src/258_AddDigits.c
/*
 * Given a non-negative integer num, repeatedly add all its digits until
 * the result has only one digit.
 *
 * For example:
 * Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
 *
 * Follow up:
 * Could you do it without any loop/recursion in O(1) runtime?
 */

int addDigits(int num) {
    if (num == 0)
        return 0;
    return (num % 9) ? (num % 9) : 9;
}
<file_sep>/src/322_CoinChange.c
/*
 * You are given coins of different denominations and a total amount of
 * money amount. Write a function to compute the fewest number of coins
 * that you need to make up that amount. If that amount of money cannot
 * be made up by any combination of the coins, return -1.
 *
 * Example 1:
 * coins = [1, 2, 5], amount = 11
 * return 3 (11 = 5 + 5 + 1)
 *
 * Example 2:
 * coins = [2], amount = 3
 * return -1.
 *
 * Note:
 * You may assume that you have an infinite number of each kind of coin.
 */

#define MIN(a,b) (a) < (b) ? (a) : (b)
int coinChange(int *coins, int coinsSize, int amount) {
    int i, j;
    int *minCoins = malloc((amount + 1) * sizeof(int));

    minCoins[0] = 0;
    for (i = 1; i <= amount; i++) {
        minCoins[i] = 0x7fffffff;
        for (j = 0; j < coinsSize; j++) {
            if ((coins[j] <= i) && (minCoins[i - coins[j]] != 0x7fffffff)) {
                minCoins[i] = MIN(minCoins[i - coins[j]] + 1, minCoins[i]);
            }
        }
    }
    return minCoins[amount] == 0x7fffffff ? -1 : minCoins[amount];
}
<file_sep>/src/110_BalancedBinaryTree.c
/*
 * Given a binary tree, determine if it is height-balanced.
 *
 * For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
 */

#define MAX(x, y) (((x) > (y)) ? (x) : (y))
int maxDepth(struct TreeNode *node) {
    if (!node)
        return 0;
    return (MAX(maxDepth(node->left), maxDepth(node->right)) + 1);
}

bool isBalanced(struct TreeNode *root) {
    if (!root)
        return true;

    return  isBalanced(root->left) &&
            isBalanced(root->right) && 
            (abs(maxDepth(root->left) - maxDepth(root->right)) <= 1);
}
<file_sep>/src/111_MinimumDepthOfBinaryTree.c
/*
 * Given a binary tree, find its minimum depth.
 *
 * The minimum depth is the number of nodes along the shortest path from
 * the root node down to the nearest leaf node.
 */

int minDepth(struct TreeNode *root) {
    int a, b;
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    a = minDepth(root->left);
    b = minDepth(root->right);

    if (a == 0) return 1+b;
    else if (b == 0) return 1+a;
    else return 1 + (a > b ? b : a);
}
<file_sep>/src/005_LongestPalindromicSubstring.c
/*
 * Given a string s, find the longest palindromic substring in s. 
 * You may assume that the maximum length of s is 1000.
 *
 * Example:
 * Input: "babad"
 * Output: "bab"
 * Note: "aba" is also a valid answer.
 *
 * Example:
 * Input: "cbbd"
 * Output: "bb"
 */

inline bool isPalindrome(char *s, int begin, int end)
{
    if (begin < 0)
        return false;

    while (begin<end) {
        if (s[begin++] != s[end--])
            return false;
    }
    return true;
}

char *longestPalindrome(char *s)
{
    int i, longest = 0, len = strlen(s);
    char *res;

    for (i = 0; i < len; i++) {
        if (isPalindrome(s, i - longest - 1, i)) {
            res = s + (i - longest - 1);
            longest += 2;
        } else if (isPalindrome(s, i - longest, i)) {
            res = s + (i - longest);
            longest += 1;
        }
    }

    if (res && longest > 0)
        res[longest] = 0;
    return res;
}
<file_sep>/src/027_RemoveElement.c
/*
 * Given an array and a value, remove all instances of that value in-place
 * and return the new length.
 *
 * Do not allocate extra space for another array, you must do this by
 * modifying the input array in-place with O(1) extra memory.
 *
 * The order of elements can be changed. It doesn't matter what you leave
 * beyond the new length.
 *
 * Example:
 * Given nums = [3,2,2,3], val = 3,
 * Your function should return length = 2, with the first two elements of nums being 2.
 */

int removeElement(int *nums, int numsSize, int val) {
    int i, y;

    y = numsSize - 1;
    for (i = 0; i <= y; i++) {
        while (nums[y] == val)
            y--;

        if (i >= y)
            return y + 1;
            
        if (nums[i] == val) {
            nums[i] = nums[y--];
        }
    }
    return y + 1;
}
<file_sep>/src/121_BestTimeToBuyAndSellStock.c
/*
 * Say you have an array for which the ith element is the price of a given
 * stock on day i.
 *
 * If you were only permitted to complete at most one transaction (ie, buy
 * one and sell one share of the stock), design an algorithm to find the
 * maximum profit.
 *
 * Example 1:
 * Input: [7, 1, 5, 3, 6, 4]
 * Output: 5
 * max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be
 * larger than buying price)
 *
 * Example 2:
 * Input: [7, 6, 4, 3, 1]
 * Output: 0
 * In this case, no transaction is done, i.e. max profit = 0.
 */

int maxProfit(int *prices, int pricesSize) {
    int i, min = prices[0], maxpf = 0;
    for (i = 0; i < pricesSize; i++) {
        min = min < prices[i] ? min : prices[i];
        maxpf = maxpf < (prices[i] - min) ? (prices[i] - min) : maxpf;
    }

    return maxpf;
}
<file_sep>/src/205_IsomorphicStrings.c
/*
 * Given two strings s and t, determine if they are isomorphic.
 *
 * Two strings are isomorphic if the characters in s can be replaced to get t.
 *
 * All occurrences of a character must be replaced with another character
 * while preserving the order of characters. No two characters may map to
 * the same character but a character may map to itself.
 *
 * For example,
 * Given "egg", "add", return true.
 * Given "foo", "bar", return false.
 * Given "paper", "title", return true.
 *
 * Note:
 * You may assume both s and t have the same length.
 */

bool isIsomorphic(char *s, char *t) {
    char dict[127] = {0};
    char dict_t[127] = {0};

    while (*s && *t) {
        if (dict[*s]==0 && dict_t[*t]==0) {
            dict[*s] = *t;
            dict_t[*t] = *s;
        } else if (dict[*s] != *t) {
            return false;
        }

        s++;
        t++;
    }
    return true;
}
<file_sep>/src/357_CountNumbersWithUniqueDigits.c
/*
 * Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.
 *
 * Example:
 * Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
 *
 */

int countNumbersWithUniqueDigits(int n) {
    int i, total = 10, last = 9, availnums = 9;
    if (n == 0)
        return 1;
    if (n == 1)
        return 10;

    for (i = 2; i <= n && i <= 10; i++) {
        last *= availnums;
        total += last;
        availnums--;
    }
    return total;
}


<file_sep>/src/326_PowerOfThree.c
/*
 * Given an integer, write a function to determine if it is a power of three.
 *
 * Follow up:
 * Could you do it without using any loop / recursion?
 */

bool isPowerOfThree(int n) {
    if (n == 3 || n == 1)
        return true;
    else if (n <= 2)
        return false;
    else if (n % 3)
        return false;
    else
        return isPowerOfThree(n/3);
}
<file_sep>/src/034_SearchForARange.c
/*
 * Given an array of integers sorted in ascending order, find the starting
 * and ending position of a given target value.
 *
 * Your algorithm's runtime complexity must be in the order of O(log n).
 *
 * If the target is not found in the array, return [-1, -1].
 *
 * For example,
 * Given [5, 7, 7, 8, 8, 10] and target value 8,
 * return [3, 4].
 */

/*
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int *nums, int numsSize, int target, int *returnSize) {
    int *ret = calloc(2, sizeof(int));
    ret[0] = -1, ret[1] = -1;
    *returnSize = 2;

    int l, r, m;
    // left
    l = 0, r = numsSize - 1;
    while (l < r) {
        m = (l + r) / 2;
        if (nums[m] < target) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    if (nums[l] == target)
        ret[0] = l;
    else
        return ret;

    // right
    r = numsSize - 1;
    while (l < r) {
        m = (l + r) / 2 + 1;
        if (nums[m] > target) {
            r = m - 1;
        } else {
            l = m;
        }
    }
    ret[1] = r;
    return ret;
}
<file_sep>/src/001_TwoSum.c
/*
 * Given an array of integers, return indices of the two numbers such that
 * they add up to a specific target.
 * You may assume that each input would have exactly one solution, and you
 * may not use the same element twice.
 *
 * Example:
 * Given nums = [2, 7, 11, 15], target = 9,
 * 
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 */


#include "int_hash.h"

int* twoSum(int *nums, int numsSize, int target) {
    int i, value, *res;

    int *res = calloc(2, sizeof(int));
    hinit();

    for (i = 0; i < numsSize; i++) {
        if (hget(nums[i], &value) == 0) {
            res[0] = value;
            res[1] = i;
            return res;
        } else {
            hset(target-nums[i], i);
        }
    }
    return res;
}
<file_sep>/src/438_FindAllAnagramsInAString.c
/*
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
*/


int isAnagrams(char *s, int *map, int size)
{
    int i;
    for (i = 0; i < size; i++) {
        map[s[i]]--;
        if (map[s[i]] < 0)
            return 0;
    }
    return 1;
}

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findAnagrams(char *s, char *p, int *returnSize) {
    int i, j = 0, len_diff, *ret;
    int map[128] = {0}, tmp[128] = {0};
    size_t s_len, p_len;

    s_len = strlen(s);
    p_len = strlen(p);
    len_diff = s_len - p_len;
    *ret = calloc(s_len + 1, sizeof(int));

    for (i = 0; i < p_len; i++) {
        map[p[i]]++;
    }

    for (i = 0; i <= len_diff; i++) {
        memcpy(tmp, map, 128*sizeof(int));
        if (isAnagrams(&s[i], &tmp, p_len)) {
            ret[j++] = i;
        }
    }
    *returnSize = j;
    return ret;
}
<file_sep>/src/172_FactorialTrailingZeroes.c
/*
 * Given an integer n, return the number of trailing zeroes in n!.
 *
 * Note: Your solution should be in logarithmic time complexity.
 */

int trailingZeroes(int n) {
    if (n == 0)
        return 0;

    return (n / 5) + trailingZeroes(n / 5);
}
<file_sep>/src/100_SameTree.c
/*
 * Given two binary trees, write a function to check if they are the same
 * or not.
 *
 * Two binary trees are considered the same if they are structurally
 * identical and the nodes have the same value.
 */

bool isSameTree(struct TreeNode *p, struct TreeNode *q) {
    if (!p && !q)
		return true;
    if (!p || !q)
		return false;

    if (p->val != q->val)
		return false;

    if (isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
        return true;
    else
        return false;
}
<file_sep>/src/076_MinimumWindowSubstring.c
/*
 * Given a string S and a string T, find the minimum window in S which
 * will contain all the characters in T in complexity O(n).
 *
 * For example,
 * S = "ADOBECODEBANC"
 * T = "ABC"
 * Minimum window is "BANC".
 *
 * Note:
 * If there is no such window in S that covers all characters in T, return
 * the empty string "".
 *
 * If there are multiple such windows, you are guaranteed that there will
 * always be only one unique minimum window in S.
 */

#define MIN(a,b) a < b ? a : b
char* minWindow(char *s, char *t) {
    int map[128];
    int i, j, min = 0x7fffffff, tmp_min = 0x7fffffff, total;
    char *begin, *end, *head;

    for (i = 0; i < 128; i++) {
        map[i] = 0;
    }

    total = strlen(t);
    for (i = 0; i < total; i++) {
        map[t[i]]++;
    }

    begin = end = s;
    while(*end) {
        if (map[*end++]-- > 0)
            total--;
        while (total == 0) {
            if ((tmp_min = end - begin) < min) {
                head = begin;
                min = tmp_min;    
            };

            if (map[*begin++]++ == 0)
                total++;
        }
    }

    if (min != 0x7fffffff)
        return strndup(head, min);
    return "";
}
<file_sep>/src/021_MergeTwoSortedLists.c
/*
 * Merge two sorted linked lists and return it as a new list. The new list
 * should be made by splicing together the nodes of the first two lists.
 *
 * Example:
 * Input: 1->2->4, 1->3->4
 * Output: 1->1->2->3->4->4
 */

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *getNextNode(struct ListNode **a, struct ListNode **b) {
    struct ListNode *ret;

    if ((*a)->val <= (*b)->val) {
        ret = *a;
        *a = ret->next;
    } else {
        ret = *b;
        *b = ret->next;
    }
    return ret;
}


struct ListNode* mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode *head;
    struct ListNode *curr;

    if (!l1 && !l2)
        return NULL;
    else if (!l1)
        return l2;
    else if (!l2)
        return l1;

    head = getNextNode(&l1, &l2);
    curr = head;

    while (l1 && l2) {
        curr->next = getNextNode(&l1, &l2);
        curr = curr->next;
    }
    if (l1) {curr->next = l1;}
    if (l2) {curr->next = l2;}

    return head;
} 
<file_sep>/src/086_PartitionList.c
/*
 * 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.
 */

struct ListNode* partition(struct ListNode *head, int x) {
    struct ListNode d1, d2;
    struct ListNode *p1, *p2;

    p1 = &d1;
    p2 = &d2;

    while (head) {
        if (head->val < x) {
            p1->next = head;
            p1 = p1->next;
        } else {
            p2->next = head;
            p2 = p2->next;
        }
        head = head->next;
    }

    p2->next = NULL;
    p1->next = d2.next;
    return d1.next;
}
