## LeetCode Problem:Flatten Binary Tree to Linked List

We can notice that in the flattened tree, each sub node is the successor node of it’s parent node in the pre-order of the original tree. So, we can do it in recursive manner, following the steps below:
1.if root is NULL return;
2.flatten the left sub tree of root, if there is left sub-tree;
3.flatten the right sub-tree of root, if has;
4.if root has no left sub-tree, then root is flattened already, just return;
5.we need to merge the left sub-tree with the right sub-tree, by concatenate the right sub-tree to the last node in left sub-tree.
5.1.find the last node in the left sub tree, as the left is flattened, this is easy.
5.2.concatenate the right sub-tree to this node’s right child.
5.3.move the left sub-tree to the right for root.
5.4.clear the left child of root.
6.done.

<br>
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given

```         1
/ \
2   5
/ \   \
3   4   6
```

The flattened tree should look like:

```   1
\
2
\
3
\
4
\
5
\
6
```

Code:48ms to accept with large test set.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (root == NULL) return;
//1.flat the left subtree
if (root->left)
flatten(root->left);
//2.flatten the right subtree
if (root->right)
flatten(root->right);
//3.if no left return
if (NULL == root->left)
return;
//4.insert left sub tree between root and root->right
//4.1.find the last node in left
TreeNode ** ptn = & (root->left->right);
while (*ptn)
ptn = & ((*ptn)->right);
//4.2.connect right sub tree after left sub tree
*ptn = root->right;
//4.3.move left sub tree to the root's right sub tree
root->right = root->left;
root->left = NULL;

}
};
```

Code rewrite at 2013-2-20, non-recursive version

```class Solution {
public:
void flatten(TreeNode *root) {
bool f = true;
stack t;
TreeNode *pre = NULL;
if(root) {
t.push(root);
}

while(t.size()) {
TreeNode *cur = t.top();
if(f) {
if(cur->left && cur->left != pre) {
t.push(cur->left);
} else {
f = false;
}
} else {
if(cur->right && cur->right != pre) {
t.push(cur->right);
f = true;
} else {
t.pop();
//at this time, the sub-tree of cur is flattened, so just flatten the cur
TreeNode *left = cur->left;
if(left) {
TreeNode *lastLeft = left;
while(lastLeft->right) {
lastLeft = lastLeft->right;
}
lastLeft->right = cur->right;
cur->right = left;
cur->left = NULL;
}
}
}
pre = cur;
}
}
};
```

## LeetCode题目：Convert Sorted List to Binary Search Tree

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.

```/**
* 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 {
TreeNode *formTree(ListNode *head, int count) {
if(count <= 0) return NULL;
int rootIndex = count / 2;
for(int ir = 0; ir < rootIndex; ++ir) {
rootNode = rootNode->next;
}
TreeNode *root = new TreeNode(rootNode->val);
root->right = formTree(rootNode->next, count - rootIndex - 1);
return root;
}
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function

//1. find the node count, takes O(n) time
int nodeCount = 0;
for(ListNode *cur = head; cur != NULL; cur = cur->next) {
++nodeCount;
}

//2. form the tree with the middle as the root
}
};
```

## CCI题目2-5：Find Loop

Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

<

pre>
map exmap;
}
}
return NULL;
}

int step = 0;

```//each step of walker, runner goes two.
while (pRunner) {
pRunner = pRunner->next;
if (++step == 2) {
pWalker = pWalker->next;
step = 0;
if (pRunner == pWalker) {
break;
}
}
}
if (!pRunner) {
return NULL;//no loop
}
//then they meet at the k posotion before loop started
//and the k is nodes before loop start
//so let runner back to head and with speed of 1
//they go simutaniously, when next meet, that position is the loop start point
while (pWalker) {
if (pWalker == pRunner) {
return pWalker;
}
pWalker = pWalker->next;
pRunner = pRunner->next;
}
return NULL;//something wrong```

}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
cout<<“process…”<<endl;
printList(pLoop);
cout<<“done”<<endl;
return 0;
}

map操作

```void mapTest(){
map testmap;
//insert key,val in map:
testmap[1] = true;
testmap[666] = false;
//find key in map
map::iterator it = testmap.find(1);
if (it != testmap.end()) {
//key if found in map
int key = it->first;//this is key
bool val = it->second;//this is val;
it->second = !val;
}
//delete a key
testmap.erase(1);
}
```

You have two numbers represented by a linked list, where each node contains a sin- gle digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

## CCI题目2-3:Remove Node at Middle of a Link List

Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

<

pre>
//1,2 del 0; 3,4 del 1; …
return;
}
Node *pRunner = (
bool move = false;
while (pRunner) {
pRunner = pRunner->next;
if (move) {
ppPre = &(*ppPre)->next;
}
move = !move;
}
//hold the removing one
pRunner = *ppPre;
//delete it from list
*ppPre = pRunner->next;
//delete it
delete pRunner;
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// instr = “10,9,8,7,6,5,4,3,2,1,0”;
// instr = “0,1,2,3,4,5,6,7,8,9,10”;
instr = “”;
// cin>>instr;
cout<<“process…”<<endl;
cout<<“done”<<endl;
return 0;
}

## CCI习题2-2：nTh From the last

Implement an algorithm to find the nth to last element of a singly linked list.

<

pre>
//zero based n th from the rear
Node * nThFromLast(Node *pHead, int n) {
if (n < 0) {
cout<<“n below 0″<<endl;
return NULL;
}
//1.let pRun go n position before pCur
for (int i = 0; i <= n; ++i) {
if (!pRun) {
cout<<“Not enough nodes”<<endl;
return NULL;//no enough nodes in the link list
}
pRun = pRun->next;
}
//2.go paralell untile pRun become NULL
while (pRun) {
pRun = pRun->next;
pCur = pCur->next;
}
return pCur;
}
int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
instr = “10,9,8,7,6,5,4,3,2,1,0”;
// cin>>instr;
cout<<“process…”<<endl;
if (pNth) {
cout<value<<endl;
}
cout<<“done”<<endl;
return 0;
}

## CCI习题2-1： Remove Duplicates

Remove Duplicates
Write code to remove duplicates from an unsorted linked list.
How would you solve this problem if a temporary buffer is not allowed?

<br>

<

pre>
//
// main.cpp
// CCI.2.1.RemoveDuplicate
//
// Created by Qiu Xiangyu on 12-11-14.
//

# include

using namespace std;
struct Node{
int value;
Node *next;
Node(int val):value(val),next(NULL) {;}
};
Node *strToList(string str){
int v = 0;
bool rem = false;
for (int i = 0; i < str.size(); ++i) {
char c = str[i];
if (c >= ‘0’ && c <= ‘9’) {
v = 10 * v + (c – ‘0’);
rem = true;
} else {
*ppnext = new Node(v);
ppnext = &((*ppnext)->next);
v = 0;
rem = false;
}
}
if (rem) {
*ppnext = new Node(v);
}
}
cout<<“List : “;
cout<value;
cout<<“,”;
}
}
cout<<endl;
}

while (pCur) {
Node **ppNext = &pCur->next;
while (*ppNext) {
Node *pNext = *ppNext;
if (pNext->value == pCur->value) {
*ppNext = pNext->next;
delete pNext;
pNext = NULL;
} else {
ppNext = &(*ppNext)->next;
}
}
pCur = pCur->next;
}
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// cin>>instr;
cout<<“process…”<<endl;
cout<<“done”<<endl;
return 0;
}

## LeetCode题目：Swap Nodes in Pairs

Swap Nodes in Pairs
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.

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function

while(true) {
ListNode *n0 = *ppre;
ListNode *n1 = n0->next;