Day 25, 2, 3, Add Two Numbers, Longest Substring Without Repeating Characters

Add Two Numbers
You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

-----------------------------------------
Solution #1, No extra space

/**
 * Definition for binary tree/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool increm = false;
        ListNode *re = l1;
        ListNode *pre = NULL; // for adding extra node
        while (l1 != NULL && l2 != NULL) {
            int sum = l1->val + l2->val;
            if (increm) {
                sum++;
                increm = false;
            }
            if (sum > 9) {
                l1->val = sum%10;
                increm = true;
            }else {
                l1->val = sum;
            }
            pre = l1;
            l1 = l1->next;
            l2 = l2->next;
        }
        if (l2 != NULL) {
            pre->next = l2;
            l1 = l2;
        }
        if (l1 != NULL) {
            while (increm && l1 != NULL ) {
                if ((l1->val == 9)) {
                    l1->val = 0;
                    pre = l1;
                    l1 = l1->next;
                }else {
                    l1->val = l1->val + 1;
                    increm = false;
                }
            }
        }
        // extra node
        if (increm) {
            pre->next = new ListNode(1);
        }
        return re;
    }
};

Update on July-10-2015
Solution #2, 3点可以优化代码
#1 carry可以用来当sum用
#2 loop的终止条件配合loop内的判断
#3 dummy node

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0), *itr = dummy;
        int carry = 0;
        while (l1 != NULL || l2 != NULL) {
            if (l1 != NULL) {
                carry += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL) {
                carry += l2->val;
                l2 = l2->next;
            }
            
            ListNode *node = new ListNode(carry % 10);
            carry /= 10;
            itr->next = node;
            itr = itr->next;
        }
        if (carry) {
            ListNode *node = new ListNode(1);
            itr->next = node;
        }
        
        return dummy->next;
    }
};

Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
--------------------------------------
O(n), two pointers:
set flag[start++] to false, flag[end++] to true

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool matrix[256] = { false };
        int start=0;
        int maxSub=0, curMax=0;
        for (int i=0;i<s.length();i++) {
            if (matrix[s[i]]) {
                maxSub = max(maxSub,curMax);
                while (s[start] != s[i]) {
                    matrix[s[start]] = false;
                    start++;
                    curMax--;
                }
                start++;
            }else {
                matrix[s[i]] = true;
                curMax++;
            }
        }
        return max(maxSub,curMax);
    }
};