206. Reverse Linked List (easy). !!

Q:

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

A:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
用dummy header
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode header;
        while (head) {
            auto tmp = head;
            head = head->next;
            tmp->next = header.next;
            header.next = tmp;
        }
        return header.next;
    }
};


或者把 新的head，不用 dummy header， 而是指向最新的head. 只是尽量晚赋值
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* newHead = nullptr;
        while (head) {
            ListNode* nextNode = head->next;
            head->next = newHead;
            newHead = head;
            head = nextNode;
        }
        return newHead;
    }
};



**********Mistakes*************
ListNode *header(0);  ---------> this grammar is WRONG. 
It initializes header as a null pointer (nullptr) because:
header is a pointer (ListNode*).
0 is an integer literal, which implicitly converts to nullptr in C++ when assigned to a pointer.
Thus header is equivalent to 
          ListNode* header = nullptr; // Explicitly setting it to nullptr

This means header->next is an invalid operation because header is nullptr.


Correct Way to Create a Dummy Node
If you meant to create an actual ListNode object, you should write:
      ListNode dummy(0);  // Correct: Creates an actual ListNode

or use dynamic allocation:

      ListNode* header = new ListNode(0); // Allocates a real ListNode on the heap

Addictive Number

Q:
Problem (Epic): Additive numbers are defined to be a positive integer whose digits form an additive sequence. E.g. 11235 (1+1=2, 1+2=3, 2+3=5). What makes it difficult is that 12,122,436 is also one (12+12=24, 12+24=36). Given a range of integers, find all the additive numbers in that range..


A:
自己的思路是先确定是几位的数字，例如从 1 到99999，我们就分别设置数组长为1 到5.

然后对那么长的数组，分别求addative number. 再检查是否within range 



XXX number  -------- sorry (I forget the name ):
find all XXX number within range [low high]
XXX number is defined as :
  each adjacent position will differ only 1.   for example 8798 is a XXX number,  890 is NOT.

permutaion II
Given a string, print all its permutations, (only lower case character can be permuted)


Contagious patient
就是一个party,互相握手。 有一个人开始有传染病。 最终多少人会有传染病？
输入是一个数值， 和一个2D array.

Digit Counts

Q:
Count the number of k's between 0 and n. k can be 0 - 9.

Example

if n=12, in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we have FIVE 1's (1, 10, 11, 12)

A:

205. Isomorphic Strings -E

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.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Note:
You may assume both s and t have the same length.

A:
就是两个一一映射的关系。
用2个mapping就行了

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        return helper(s,t) && helper(t,s);
    }
private:
    bool helper(string s, string t)
    {
        map<char, char> mymap;
        for(int i =0;i<s.length();++i)
        {
            char ch1 = s[i];
            char ch2 = t[i];
            if(mymap.find(ch1)==mymap.end()) // first time find
            {
                mymap.insert({ch1,ch2});
            }else{
                if(mymap.find(ch1)->second != ch2)
                {
                    return false;
                }
            }
        }
        return true;
    }
};

通常的做法就是用2个map，这样就不用call 2 遍。

还有就是不用map, 直接用array, 用char 的值做index.