一般 ： cur->next的前面一定要注意cur本身是否为NULL， 加条件 cur != NULL.
while(cur && cur->next) 如果需要写cur->next，那么一定有cur伴随。
2. Linklist 里面经常会出现和数字有关的问题， 比如 m,n 之间， 第K个，...我自己是很小心这种在linklist里面带数字的题目的，因为这些数字的变化很容易出错， 对于这类题目，为了避免出错，可以先拿一个最简单的case来过一下，比如：当m == 1或者K==1的时候，这样的话问题就会简化很多，也容易找到变化规律。
Linked list 题目 high level 分析：
Linked list 常见的几种类型： single linked list, circular linked list, double linked list
所有题目都可以应用在这三个类型的链表中，
1. 大体上就是pre, cur, next指针的变换，不同要求，变换的过程也不一样。
2. delete/remove nodes in linked list
3. insert nodes in linked list
4. reverse nodes
5. linked list length 的应用
6.slow + fast pointer 应用在Linked list里
7. linked list as a Graph
8. double linked list + hash map
常用的技巧： dummy node
常常需要考虑的corner case: 链表头尾, 链表为空， 含有数字的题目，看看数字==1 或者数字==链表长 怎么办
1. Remove/Delete from linked list
Q1: Remove Nth Node from end of linked list
//1. pre , cur, next
//2. head may be changed--> dummy node
//3. slow , fast to find the nth node
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == NULL) return NULL;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* fast = head;
ListNode* slow = head;
ListNode* pre = dummy;
while (n) {
fast = fast->next;
n--;
}
while (fast) {
fast = fast->next;
pre = slow;
slow = slow->next;
}
ListNode* next = slow->next;
pre->next = next;
slow->next = NULL;
delete slow;
return dummy->next;
}
Q2: Remove linked list element
//1. pre, cur, next
//2. head may be changed---> dummy head
//3. continues value doesn't matter
ListNode* removeElements(ListNode* head, int val) {
if (head == NULL) return NULL;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
while (cur) {
if (cur->val == val) {
pre->next = cur->next;
} else {
pre = cur;
}
cur = cur->next;
}
return dummy->next;
delete dummy;
}
Q3: Remove duplicates from linked listI
//1.no need to use dummy node
//2. cur, next
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* next = cur->next;
while (next) {
if (cur->val != next->val) {
cur->next = next;
cur = next;
}
next = next->next;
}
cur->next = next;
return head;
}
Q4: Remove duplicates from linked listII
//1. dummy node
//2. pre, cur
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = head;
ListNode* pre = dummy;
while (cur && cur->next) {
if (cur->next != NULL && cur->next->val == cur->val) {
while (cur->next != NULL && cur->next->val == cur->val) {
cur = cur->next;
}
pre->next = cur->next;
} else {
pre = cur;
}
cur = cur->next;
}
return dummy->next;
delete dummy;
}
Q5：Delete Node in a linked list
这是个很tricky的题目，有小技巧，只给定删除的节点，但是不给head,要求删除非tail的node.
这个题目里面不需要用到pre node， 算是一种特殊算法吧，利用node value可以改变的特点。
void deleteNode(ListNode* node) {
if (node == NULL) return;
node->val = node->next->val;
node->next = node->next->next;
}
删除多个List 里面符合要求的node:
Q6: remove all the vowels in a linked list:
vowels: a,e,i,o,u
class ListNode{
char val;
ListNode* next;
ListNode(char val) {
this->val = val;
next = NULL;
}
}；
bool isVowel(ListNode* node) {
if (node->val == 'a' || node->val == 'e' || node->val == 'i' || node->val == 'o' || node->val == 'u') {
return true;
} else {
return false;
}
}
ListNode* removeVowels(ListNode* head) {
if (head == NULL) return NULL;
ListNode* dummy = new ListNode('X');
dummy->next = head;
ListNode* pre = dummy;
while (head) {
if (isVowel(head)) {
pre->next = head->next;
} else {
pre = head;
}
head = head->next;
}
return dummy->next;
}
ListNode* removeVowels(ListNode* head, vector<int> idel) {
if (head == NULL) return NULL;
ListNode* dummy = new ListNode('X');
dummy->next = head;
ListNode* pre = dummy;
int index = 0;
int i = 0;
while (head && i < idel.size()) {
if (i < idel.size() && index == idel[i]) {
pre->next = head->next;
i++;
} else {
pre = head->next;
}
index++;
head = head->next;
}
return dummy->next;
}
merge list, 如果两个list需要merge到一起形成一条list,那么可以利用dummy head 来代表merge 后的list的head， 通过cur , 代表tail of the merge list来对两个链表进行操作。
Q1: merge two sorted list
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;//tail of the merge list
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
cur = l1;
l1 = l1->next;
} else {
cur->next = l2;
cur = l2;
l2 = l2->next;
}
}
if (l1) {
cur->next = l1;
} else {
cur->next = l2;
}
return dummy->next;
}
Q2: merge k sorted list
这个题目是由merge two sorted list general 化的题目， 由2--》 k， 我们一定是可以通过利用2的解来得到k的解，这种divide and conquer的思想很重要，要求K，我们可以解决2, 然后由2的解来推出K的解。
class Solution {
private:
ListNode* merge(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
cur = l1;
l1 = l1->next;
} else {
cur->next = l2;
cur = l2;
l2 = l2->next;
}
}
if (l1) {
cur->next = l1;
} else {
cur->next = l2;
}
return dummy->next;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0) return NULL;
int len = lists.size();
while (len > 1) {
for (int i = 0; i < len/2; i++) {
lists[i] = merge(lists[i], lists[i+len/2]);
}
if (len % 2) {
lists[len/2] = lists[len-1];
len = len/2 + 1;
}
else len = len/2;
}
return lists[0];
}
};
follow up:
de-duplicate at the same time of the merge operation:
I think I just need to modify the merge function, when the two elements are the same, we keep moving cur, until we meet a different element.
时间复杂度： 下面那个while循环，进行log(n)次， 每次进while, for 循环进行n/2次，merge时间复杂度是O(m) m: 链表长度，所以总时间复杂度是O(m*n*logn)
这个题目也可以用priority_queue来做，Initial state是所有list的head, 这种做法时间复杂度是一样的，但是需要额外的O(n)的空间。
所以还是divide and conquer的做法好一些。
3. insert in linked list
Q1: insert in sorted circular linked list
linkist的题目也需要考虑一些corner case:
insert的corner case 一般是可能会插在linklist的head前面，所以需要一个dummy node来解决
但是对于这个circular link list的话，插入就不只是只有insert before head这一个corner case 可以解决了， 对于插入tail 和插入head都是需要特别考虑的， 因为 插入tail和head都需要改变两个指针， 一个head，一个tail,这两个指针的指向都会发生变化， 但是如果插入是中间位置，那么只需要变化pre指针的指向。
ListNode* insertInCircularLinkList(ListNode* head, int val ) {
ListNode* nNode = new ListNode(val);
if (head == NULL) return nNode;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* tail = NULL;
ListNode* cur = head;
ListNode* pre = dummy;
//has duplicate node
while (cur->next->val >= cur->val) {
if (val <= cur->val) {
pre->next = nNode;
nNode->next = cur;
if (cur != head) {
return dummy->next;
}
}
pre = cur;
cur = cur->next;
}
tail = cur;
if (val < head->val) {
head = nNode;
tail->next = nNode;
} else {
tail->next = nNode;
nNode->next = head;
}
return dummy->next;
}
4.Reverse Linked list
Q1: reverse single linked list
M1: iterative'
M2: recursion
M3: Stack
Q1-3 reverse circular linked list
跟reverse single linked list 是类似的，只是需要一个结束条件， 当head 第二次遍历的时候就需要停下来。
ListNode* reverseCircularLinkedList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* stop = cur;
while (true) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
if (cur == stop) {
break;
}
}
return pre;
}
Q1-2 reverse double linked list
M1: recursion
recursion的写法很容易，思想和single linked list差不多，但是问题是double linked list 需要改变指针指向更复杂一些。
ListNode* reverseDoubleLinkedList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* next = cur->next;
//before caculating the subproblem, should set next->pre to be NULL first, because 2 's pre is no longer point to cur. otherwise, will cause a circular linked list
next->pre = NULL;
ListNode* nNode = reverseDoubleLinkedList(next);
next->next = cur;
cur->pre = next;
cur->next = NULL;
return nNode;
}
iterative 的方法比recursion的方法更容易理解。
ListNode* reverseDoubleLinkedList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* pre = NULL;
while (cur) {
ListNode* next = cur->next;
cur->next = pre;
cur->pre = next;
pre = cur;
cur = next;
}
return pre;
}
整个reverse跟single linked list 类似。
Q2: reverse single Linked listII (只reverse 指定区间内的Nodes)
!!!!这一题做了好久啊！有没有逻辑清晰的做法？？？
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == NULL || head->next == NULL) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = head;
ListNode* node1 = cur;
ListNode* node2 = cur;
ListNode* pre = dummy;
ListNode* tmp = cur;
ListNode* next = cur;
int l1 = m;
while (cur) {
if (m > 1) {
pre = cur;
cur = cur->next;
m--;
} else {
node1 = cur;
break;
}
}
next = cur->next;
while (cur) {
if (n > l1) {
tmp = next->next;
next->next = cur;
cur = next;
next = tmp;
n--;
} else {
node2 = cur;
break;
}
}
tmp = next;
pre->next = node2;
node1->next = tmp;
return dummy->next;
}
};
代码重构之后：由于m, n都是valid的，所以不需要考虑在变量m->n过程中cur会变成NULL的情况。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == NULL || head->next == NULL) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* node1 = head;
ListNode* pnode1 = dummy;
int step = n-m;
while (m > 1) {
pnode1 = node1;
node1 = node1->next;
m--;
}
ListNode* pre = node1;
ListNode* cur = pre->next;
while (step) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
step--;
}
ListNode* node2 = pre;
pnode1->next = node2;
node1->next = cur;
return dummy->next;
}
};
这两段代码比较起来，后者清晰很多，其实上面代码问题是很多变量都全部放在程序一开始，导致最后看起来很繁琐，还不如在哪段程序需要用到哪个变量的时候再开始定义，这样想的逻辑也会清晰一些，变量的定义都给其一个明确的含义，不要有具体含义的变量重复使用，貌似看起来省空间，其实写出来的代码可读性和逻辑性非常差，特别容易出错。
再做算法题的时候，变量含义要稳定，不要仅仅为了程序运行结果正确而乱改变量，或者使得变量的含义变来变去，这样写出来的代码是垃圾，可读性和理解性极差无比！
Q3: reverse Linked list in k group
其实这个题目是下面swap nodes in pair的拓展，指针变化的思想是相同的， 下面那个题目搞清楚，这个题目就很简单了。
class Solution {
private:
//1. DUMMY
//2. pre, cur, next
ListNode* reverse(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* next = cur->next;
ListNode* nodeN = reverse(next);
next->next = cur;
cur->next = NULL;
return nodeN;
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == NULL) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
int count = 1;
ListNode* next = NULL;
while (cur) {
ListNode* end = cur;
while (count < k && end) {
end = end->next;
count++;
}
if (count == k && end != NULL) {
next = end->next;
end->next = NULL;
pre->next = reverse(cur);
cur->next = next;
pre = cur;
cur = next;
count = 1;
} else if (end == NULL) {
break;
}
}
return dummy->next;
}
};
Facebook Phone interview question:
上一题的变形：
reverse nodes in k groups of odd number of group: single linked list k 个 k 个分组，反转奇数组， 对于最后不足奇数组的，也反转。
class Solution {
private:
//1. DUMMY
//2. pre, cur, next
ListNode* reverse(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* next = cur->next;
ListNode* nodeN = reverse(next);
next->next = cur;
cur->next = NULL;
return nodeN;
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == NULL) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
int count = 1;
ListNode* next = NULL;
int odd = 1;
while (cur) {
ListNode* end = cur;
while (count < k && end) {
end = end->next;
count++;
}
if (count == k && end != NULL ) {
next = end->next;
if (odd%2) {
end->next = NULL;
pre->next = reverse(cur);
cur->next = next;
pre = cur;
} else {
pre = end;
}
odd++;
cur = next;
count = 1;
} else if (end == NULL) {
// break;
if(odd%2) {
pre->next = reverse(cur);
cur->next = NULL;
}
break;
}
}
return dummy->next;
}
};
Q4: swap nodes in pair
//1.dummy
//2. pre, next, cur
//3. 2 end condition
ListNode* swapPairs(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
ListNode* next = cur;
while(cur) {
if (cur->next) {
next = cur->next->next;
} else {
break;
}
pre->next = cur->next;
cur->next->next = cur;
cur->next = next;
pre = cur;
cur = next;
}
return dummy->next;
}
指针的操作顺序能减少一些变量的使用。
Reorder List
Q5: Rotate List
这个题目应该首先想到：
1. general 的做法，就是不考虑corner case的情况
2. k的取值， corner cases， k == 0, k == len, 这个题目就只有这两种corner case, 而且这两种corner case其实是统一的。
Rotate 的问题和shift 类似，如果rotate的位移超过长度，就对长度取mod, 对于位移长度为0的话需要特殊处理，作为一个corner case条件。
class Solution {
private:
int getlen(ListNode* head) {
int len = 0;
while (head) {
head = head->next;
len++;
}
return len;
}
public:
//1. dummy
//2. rotate : mod len
//3. pre, tail, cur, slow, fast
ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL || head->next == NULL) {
return head;
}
int len = getlen(head);
k = k % len;
if (k == 0) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* slow = head;
ListNode* fast = head;
ListNode* tail = NULL;
while (k) {
fast = fast->next;
k--;
}
while (fast) {
tail = fast;
fast = fast->next;
pre =slow;
slow = slow->next;
}
tail->next = dummy->next;
pre->next = NULL;
dummy->next = slow;
return dummy->next;
delete dummy;
}
};
Q6: Sort List
要求O(nlogn)的时间复杂度： merge sort
class Solution {
private:
ListNode* merge(ListNode* left, ListNode* right) {
if (left == NULL) return right;
if (right == NULL) return left;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while(left && right) {
if (left->val < right->val) {
cur->next = left;
cur = left;
left = left->next;
} else {
cur->next = right;
cur = right;
right = right->next;
}
}
if (left) {
cur->next = left;
} else {
cur->next = right;
}
return dummy->next;
}
public:
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* fast = head;
ListNode* slow = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
ListNode* left = head;
ListNode* right = slow->next;
slow->next = NULL;
left = sortList(left);
right = sortList(right);
ListNode* rst = merge(left, right);
return rst;
}
};
Q7: Reorder List
这个题目是由几类linked list的操作组合成的。
class Solution {
private:
ListNode* reverse(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* next = cur->next;
ListNode* nodeN = reverse(next);
next->next = cur;
cur->next = NULL;
return nodeN;
}
ListNode* interMerge(ListNode* left, ListNode* right) {
if (left == NULL) return right;
if (right == NULL) return left;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (left && right) {
cur->next = left;
cur = left;
left = left->next;
cur->next = right;
cur = right;
right = right->next;
}
if (left) {
cur->next = left;
} else {
cur->next = right;
}
return dummy->next;
}
public:
//even or odd length
void reorderList(ListNode* head) {
if (head == NULL || head->next == NULL) return;
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
ListNode* right = slow->next;
slow->next = NULL;
ListNode* left = head;
right = reverse(right);
head = interMerge(left, right);
return;
}
};
Q8： partition List
//get the small list and large list out of the original list, the process is like merge lists. use a dummy node as head.
ListNode* partition(ListNode* head, int x) {
if (head == NULL || head->next == NULL) return head;
ListNode* small = new ListNode(0);
ListNode* large = new ListNode(0);
ListNode* ssmall = small;
ListNode* llarge = large;
while (head) {
if (head->val < x ) {
ssmall->next = head;
ssmall = head;
} else {
llarge->next = head;
llarge = head;
}
head = head->next;
}
ssmall->next = large->next;
llarge->next = NULL;
return small->next;
}
Q9； palindrome list
panlindrome 应用在Linked list上面。
class Solution {
private:
ListNode* reverse(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* cur = head;
ListNode* next = cur->next;
ListNode* nodeN = reverse(next);
next->next = cur;
cur->next = NULL;
return nodeN;
}
public:
bool isPalindrome(ListNode* head) {
if (head == NULL || head->next ==NULL) return true;
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
slow->next = reverse(slow->next);
slow = slow->next;
while (slow) {
if (head->val == slow->val) {
head = head->next;
slow = slow->next;
} else {
return false;
}
}
return true;
}
};
Slow + Fast pointer :
The problems in array using slow and fast pointer to solve can also apply to linked list.
for slow and fast pointer, we have to clear that what's the definition of slow and fast and when we should move slow and when we should move fast.
3 cases of slow and fast pointer:
case1: fast moves ahead of slow and then slow and fast moves together with the same speed (e.g.: find kth node in the end of the link list)
case2: fast moves more steps than slow each time. (e.g.: find middle node, find cycle)
case3: fast and slow moves at different condition. (sliding window - 变长window)
Q1: determine the longest sub list not containing duplicate values:
sliding window: 变长window，
hashset: to check if there are duplicates
slow-fast: no duplicates
slow: when there is duplicates in the hashset, move slow
fast: when there is no duplicates in the hashset, move fast
gmax: the length of longest substring
int LongestSubListWithoutDupicates(ListNode* head) {
if (head == NULL) return 0;
ListNode* slow = head;
ListNode* fast = head;
unordered_set<int> nset;
int gmax = 0;
int len = 0;
while (fast) {
if (nset.find(fast->val) == nset.end()) {
nset.insert(fast->val);
fast = fast->next;
len++;
gmax = max(gmax, len);
} else {
while (slow && slow->val != fast->val) {
nset.erase(slow->val);
slow = slow->next;
len--;
}
if (slow) {
nset.erase(slow->val);
slow = slow->next;
len--;
}
}
}
return gmax;
}
代码重构之后：
1. we can use nset to check the duplicates, no need to use slow->val == fast->val
2. the size of hash set is the length we need, no need to set the len variabl to keep the length.
int LongestSubListWithoutDupicates(ListNode* head) {
if (head == NULL) return 0;
ListNode* slow = head;
ListNode* fast = head;
unordered_set<int> nset;
int gmax = 0;
while (fast) {
if (nset.find(fast->val) == nset.end()) {
nset.insert(fast->val);
fast = fast->next;
} else {
nset.erase(slow->val);
slow = slow->next;
}
gmax = max(gmax, (int)nset.size());
}
return gmax;
}
Q2: determine the longest sub list in a circular list not containing duplicate value
对于circular Linked list的处理， 我想到的是走两遍 linked list, 记录遍历head的次数，遍历到第三次的时候停止。 这样就相当于把circular linked list 变成两个single linked list，首尾相连了。 应该可以cover到： 1-3-2-4-2-5-1这种情况。
Q1： cycle in linked listI
bool hasCycle(ListNode *head) {
if (head == NULL|| head->next == NULL) return false;
ListNode* fast = head;
ListNode* slow = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow ) return true;
}
return false;
}
Q2： cycle in linked listII
ListNode *detectCycle(ListNode *head) {
if (head == NULL) return head;
ListNode* fast = head;
ListNode* slow = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast) break;
}
if (fast->next == NULL || fast->next->next == NULL) return NULL;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
Q3: intersection of two linked list
这个题目很重要，考的次数非常多，利用链表的长度关系来解题
还有： lowest common ancester 只有parent node， 没有head的题转化一下其实也是两个Linkedlist的intersection问题。 沿着parent 往上走。
class Solution {
private:
int getLen(ListNode* head) {
int len = 0;
while (head) {
head = head->next;
len++;
}
return len;
}
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == NULL || headB == NULL) return NULL;
int lenA = getLen(headA);
int lenB = getLen(headB);
if (lenA > lenB) return getIntersectionNode(headB, headA);
int diff = lenB - lenA;
while (diff) {
headB = headB->next;
diff--;
}
while (headA && headB && headA != headB) {
headA = headA->next;
headB = headB->next;
}
if (headA == NULL || headB == NULL) return NULL;
return headA;
}
};
Q4: Add two Numbers
两个链表已经reverse过了，直接从Head开始加就可以，利用一个carry，分三种情况，一种l1,l2都不是NULL， 另一种l1是NULL，最后是l2 是 NULL。由于head改变，所以利用一个dummy head 更加容易解题。
最后要注意，全部加完如果carry == 1， 说明最高位有一个新的node 为1.
Q5: Add two numbers II
两个链表没有reverse 过， 但是我们做加法的时候还是从低位加起。
M1: reverse two linked list, add two linked list using add two number I, then reverse the linked list back
M2：利用链表长度来解题，利用recursion。
Treat Linked list as A Graph:
Copy List
Q1: deep copy of linked list with random pointer
Serialize tree to linked list:
for this kind of question, we need to keep two extra pointer: prev and head of the new linked list.
We need these two pointer because we need to have the previous and current nodes relationship. previous and current nodes are common in linked list, and these can be used to form a linked list.
previous and current nodes can be retrieved from a kind of traversal method over the tree.
Flattern binary tree to single linked list:
left subtree should insert to between root and root->right.
recursion：
class Solution {
private:
void helper(TreeNode* root, TreeNode* &pre, TreeNode* &head) {
if (root == NULL) return;
TreeNode* right = root->right;
if (pre == NULL) {
head = root;
} else {
pre->right = root;
pre->left = NULL;
}
pre = root;
helper(root->left, pre, head);
helper(right, pre, head);
}
public:
void flatten(TreeNode* root) {
TreeNode* pre = NULL;
TreeNode* head = NULL;
helper(root, pre, head);
root = head;
}
};
iterative :
iterative 用stack来模拟 preorder 这个过程，跟recursion 有一点有很大的区别，由于preorder 在iterative过程中， right subtree在遍历左子树之前已经存进了stack中，所以在后面的遍历过程中，是可以拿到right的，所以不需要提前保存right subtree。
class Solution {
public:
void flatten(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> buf;
buf.push(root);
TreeNode* prev = NULL;
TreeNode* head = NULL;
TreeNode* cur = root;
while(!buf.empty()) {
cur = buf.top();
buf.pop();
if (prev == NULL) {
head = cur;
} else {
prev->right = cur;
prev->left = NULL;
}
prev = cur;
if (cur->right) {
buf.push(cur->right);
}
if (cur->left) {
buf.push(cur->left);
}
}
root = head;
}
};
Flattern binary tree to double linked list
void helper(TreeNode* root, TreeNode* &head, TreeNode* &pre) {
if (root == NULL) return;
helper(root->left, head, pre);
if (pre == NULL ) {
head = root;
} else {
pre->right = cur;
cur->left = pre;
}
pre = root;
helper(root->right, head, pre);
}
No comments:
Post a Comment