## 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.

```/**
* Definition for singly-linked list.
* 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;
ListNode *rootNode = head;
for(int ir = 0; ir < rootIndex; ++ir) {
rootNode = rootNode->next;
}
TreeNode *root = new TreeNode(rootNode->val);
root->left = formTree(head,rootIndex);
root->right = formTree(rootNode->next, count - rootIndex - 1);
return root;
}
public:
TreeNode *sortedListToBST(ListNode *head) {
// 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
return formTree(head, nodeCount);
}
};
```

## 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>
Node * findLoop(Node *pHead) {
map exmap;
while (pHead) {
if (exmap.find(pHead) != exmap.end()) {
return pHead;
}
exmap[pHead] = true;
pHead = pHead->next;
}
return NULL;
}

Node *findLoopEx(Node *pHead) {
Node *pRunner = pHead;
Node *pWalker = pHead;
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
pRunner = pHead;
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”;
Node *phead = loopList(10, 8);
printList(phead);
cout<<“process…”<<endl;
Node *pLoop = findLoop(phead);
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);
}
```

## CCI题目2-4：Add Two Numbers in Link List

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>
void RemoveMiddle(Node **ppHead) {
//1,2 del 0; 3,4 del 1; …
if (!(ppHead)) {
return;
}
Node *pRunner = (
ppHead)->next;
Node **ppPre = ppHead;
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;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
RemoveMiddle(&phead);
printList(phead);
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;
}
Node *pCur = pHead;
Node *pRun = pHead;
//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;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
Node *pNth = nThFromLast(phead,10);//test 10,9,5,1,0,12,-11
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.
FOLLOW UP
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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

# include

using namespace std;
struct Node{
int value;
Node *next;
Node(int val):value(val),next(NULL) {;}
};
Node *strToList(string str){
Node *phead = NULL;
Node **ppnext = &phead;
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);
}
return phead;
}
void printList(Node *phead) {
cout<<“List : “;
while (phead) {
cout<value;
if (phead->next) {
cout<<“,”;
}
phead = phead->next;
}
cout<<endl;
}

void removeDuplicate(Node *pHead) {
Node *pCur = pHead;
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;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
removeDuplicate(phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

## LeetCode题目：Swap Nodes in Pairs

Swap Nodes in Pairs
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;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode **ppre = &head;

while(true) {
ListNode *n0 = *ppre;
if(NULL == n0) return head;
ListNode *n1 = n0->next;
if(NULL == n1) return head;

//swap n0 and n1
*ppre = n1;
n0->next = n1->next;
n1->next = n0;
ListNode *next = n1->next;
ppre = &(n0->next);
}

return head;
}
};
```

## LeetCode题目：Remove Duplicates from Sorted List II

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.

```/**
* 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) {
ListNode *root = NULL;
ListNode **ppNext = &root;
while(head) {
if(head->next == NULL || head->next->val != head->val) {
*ppNext = head;
ppNext = &(head->next);
head = head->next;
} else {
int val = head->val;
do {
head = head->next;
} while(head != NULL && head->val == val);
}
}
*ppNext = NULL;
return root;
}
};
```

## LeetCode题目：Remove Duplicates from Sorted List

Remove Duplicates from Sorted List
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.

```/**
* 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) return NULL;
ListNode *last = head;
ListNode *cur = last->next;
while(cur) {
if(cur->val != last->val) {
last->next = cur;
last = cur;
}
cur = cur->next;
}
last->next = NULL;
return head;
}
};
```

## LeetCode题目：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
ListNode *pL = NULL, *pR = NULL;
ListNode *pLastR = NULL;
ListNode **ppL = &pL, **ppR = &pR;
while(head) {
if(head->val < x) {
//go to left
*ppL = head;
ppL = &(head->next);
} else {
//go to right
*ppR = head;
pLastR = head;
ppR = &(head->next);
}

head = head->next;
}
//link left with right
*ppL = pR;
if(pLastR) pLastR->next = NULL;
return pL;
}
};
```

## LeetCode题目：Merge Two Sorted Lists

Merge Two Sorted Lists
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.

```/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *proot = NULL;
ListNode **pplast = &proot;
while(l1 || l2){
if(l1) {
ListNode *minNode;
if(!l2 || l1->val <= l2->val){
//l1 is min
minNode = l1;
l1 = l1->next;
} else if(l2) {
//l2 is min
minNode = l2;
l2 = l2->next;
}
//proceed root
*pplast = minNode;
pplast = &(minNode->next);
} else {
//l1 is empty
*pplast = l2;
break;
}
}
return proot;
}
};
```

## Leetcode题目：Add Two Numbers, 两个链表数相加

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

```/**
* 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
ListNode rootNode(0);
ListNode *pCurNode = &rootNode;
int forward = 0;
while(l1||l2)
{
int v1 = (l1 ? l1->val : 0);
int v2 = (l2 ? l2->val : 0);
int sum = v1 + v2 + forward;
forward = sum / 10;
sum = sum % 10;
ListNode *pNode = new ListNode(sum);
pCurNode->next = pNode;
pCurNode = pNode;
if(l1) l1 = l1->next;
if(l2) l2 = l2 ->next;
}
if(forward > 0)
{
ListNode *pNode = new ListNode(forward);
pCurNode->next = pNode;
}
return rootNode.next;
}
};
```

Code rewrite at 2012-12-26, Simpler

```class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
int overflow = 0;
ListNode *ret = NULL;
ListNode **pnode = &ret;
while(l1 && l2) {
int val = l1->val + l2->val + overflow;
overflow = val / 10;
*pnode = new ListNode(val % 10);
pnode = &((*pnode)->next);
l1 = l1->next;
l2 = l2->next;
}
ListNode *lremain = l1 ? l1 : l2;
while(lremain) {
int val = lremain->val + overflow;
overflow = val / 10;
*pnode = new ListNode(val % 10);
pnode = &((*pnode)->next);
lremain = lremain->next;
}
if(overflow > 0) {
*pnode = new ListNode(overflow);
}
return ret;
}
};
```

New C solution at 2016-04-22

```/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
struct ListNode* root = NULL;
struct ListNode** next = NULL;
int overflow = 0;
while(l1 || l2 || overflow > 0){
// calculation
int v = overflow;
if(l1){ v += l1->val; l1 = l1->next;}
if(l2){ v += l2->val; l2 = l2->next;}
overflow = v / 10;
v = v % 10;
// new node
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = v;
newNode->next = NULL;
if(next) *next = newNode;
next = &(newNode->next);
if(root == NULL) root = newNode;
}
return root;
}
```

New Ruby solution at 2016-04-22

```# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def add_two_numbers(l1, l2)
return l1 if l2.nil?
return l2 if l1.nil?
root = nil
tail = nil
overflow = 0
while l1 || l2 || overflow > 0 do
v = overflow
unless l1.nil?
v += l1.val
l1 = l1.next
end
unless l2.nil?
v += l2.val
l2 = l2.next
end
overflow = v / 10
v = v % 10
new_node = ListNode.new(v)
root = new_node if root.nil?
tail.next = new_node unless tail.nil?
tail = new_node
end
root
end
```