Chapter 9 Linked List
As a data structure, linked list can be considered as a one dimension, simplified, or flattened binary tree.
Related Algorithms:
- Two pointers/ three pointers
- Recursion
The algorithm idea is pretty much like array. The difficulty is mainly from the non-random-accessiblity of list node. The most error-prone part is connecting the node correctly!
链表操作基本技巧之一: reverse linked list
最后p就是新的head.
链表操作基本技巧之二: 找Lower Median,中点
ListNode* fast = head, *slow = head;
while (fast && fast->next && fast->next->next)
fast = fast->next->next, slow = slow->next;最后slow就是中点.
链表操作基本技巧之三: delete a node
There are two kinds of delete: delete current node or next node
- 删除当前元素(current node):
p->next = c->nextorc->val=c->next->val, c->next=c->next->next;
这个方法有个缺点不能删除尾巴,所以要慎用.做这个题体会一下.
- 删除下一个元素(next node):
c->next=c->next->next
Leetcode Problems:
328 Odd Even Linked List 37.4% Medium
237 Delete Node in a Linked List 43.6% Easy
234 Palindrome Linked List 27.8% Easy
206 Reverse Linked List 39.1% Easy
203 Remove Linked List Elements 28.4% Easy
160 Intersection of Two Linked Lists30.2% Easy
148 Sort List 24.6% Medium
147 Insertion Sort List 29.1% Medium
143 Reorder List 22.6% Medium
142 Linked List Cycle II 31.5% Medium
141 Linked List Cycle 36.9% Medium
138 Copy List with Random Pointer 26.0% Hard
114 Flatten Binary Tree to Linked List 30.9% Medium
109 Convert Sorted List to Binary Search Tree 30.2% Medium
92 Reverse Linked List II 27.7% Medium
86 Partition List 29.3% Medium
83 Remove Duplicates from Sorted List 36.6% Easy
82 Remove Duplicates from Sorted List II 26.8% Medium
61 Rotate List 22.8% Medium
23 Merge k Sorted Lists 23.2% Hard
21 Merge Two Sorted Lists 35.2% Easy
19 Remove Nth Node From End of List 29.2% EasyTips:
while(head){} - after while loop, head is null(last node is processed inside while).
while(head->next){} - after while loop, head is the last node(last node is not processed inside while).
Dummy node \(d\) - make sure not to lose track of head node when looping the list. The code is normally like the following:
For recursive method, be careful to the . Don’t write redundant code for the termination condition! Ensure code is clean and neat!
Naming Convention:
d - dummy node
c - current node, used to loop through the list
h - head of linked list
p - previous node
n - next node
nn - next next node
t - tmp nodeLinked List Problems - Stanford CS Education Library
9.1 Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/
9.1.1 Iterative
struct Solution {
ListNode* reverseList(ListNode* head) {
ListNode *p = NULL, *c = head, *n;
while (c) n = c->next, c->next = p, p = c, c = n;
return p;
}
};Note:
\(p\) is initialized to the next node of new tail, but it will finally become the new head.
This kind of in-place chaining assignment has a pattern like the following graph. We can see the same pattern in Rotate Image problem.
9.1.2 Recursive
struct Solution {
ListNode* reverseList(ListNode* head) {
auto pr = dfs(head);
return pr.first;
}
// new head, new tail
pair<ListNode*,ListNode*> dfs(ListNode* head){
if (!head or !head->next)
return {head, head};
auto pr = dfs(head->next);
pr.second->next = head, head->next= NULL;
return {pr.first, head};
}
};9.2 Partition List
https://leetcode.com/problems/partition-list/
Use p to move from head to end and compare each value with x Create two dummy point, one is used to link points that are <x, another is to link points that are >=x.
struct Solution {
ListNode* partition(ListNode* head, int x) {
ListNode d1(0), d2(0);
ListNode *c1=&d1, *c2=&d2;
while (head){
if (head->val < x)
c1->next = head, c1 = head;
else
c2->next = head, c2 = head;
head = head->next;
}
c1->next = d2.next;
c2->next = nullptr; //!!
return d1.next;
}
};Draw a graph to analyze the whole process, or line 13 is very easy to be forgotten!
9.3 Palindrome Linked List
https://leetcode.com/problems/palindrome-linked-list/
http://www.cnblogs.com/grandyang/p/4635425.html
No matter node number is even or odd, we reverse nodes in \([LM->next, tail]\).
Actually it is not necessary to connect the reversed part, or deal with slow->next.
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode* fast = head, *slow = head;
while (fast && fast->next && fast->next->next)
fast = fast->next->next, slow = slow->next;
ListNode* p = NULL, *c = slow->next, *n;
while (c) n = c->next, c->next = p, p = c, c = n;// reverse LL
while (p) {
if (head->val != p->val) return false;
head = head->next, p = p->next;
}
return true;
}9.4 143. Reorder List
Given a singly linked list L: L0?L1?…?Ln-1?Ln, reorder it to: L0?Ln?L1?Ln-1?L2?Ln-2?…
You must do this in-place without altering the nodes’ values.
For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.
https://leetcode.com/problems/reorder-list/
class Solution {
public:
void reorderList(ListNode* head) {
if(!head || !head->next || !head->next->next) return; //if(!head) return;
ListNode *fast=head, *slow=head;
while(fast && fast->next && fast->next->next)
fast=fast->next->next, slow=slow->next;
ListNode* p=0, *c=slow->next, *n;
slow->next=0;
while(c) n=c->next, c->next=p, p=c, c=n;
ListNode d(0);
c=&d;
while(head){
c->next=head, head=head->next, c=c->next;
if(p) c->next=p, p=p->next, c=c->next;
}
//return d.next;
}
};2017(7-9月) 码农类 硕士 全职 Facebook - 猎头 - 技术电面 |Other在职跳槽
刷题 143 原题印度小哥,说了很多,给我30min coding.前后各交流15min
先说O n^2 解, 又说里On 解,然后开始写
猎头领英上联系的,不知道是不是只能在infra下面选组的
题不难,但不在tag里,如果面同一个组但同学可以看看linked list相关题 求问各位大神白板速度怎么提升,我感觉自己还是废话太多.
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=292345
9.5 328. Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
Note:
The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on …
https://leetcode.com/problems/odd-even-linked-list/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode d0(0), d1(0);
ListNode *c0=&d0, *c1=&d1;
int n=1;
while(head){
if(n&1) c1->next=head, c1=c1->next;
else c0->next=head, c0=c0->next;
auto t=head;
head=head->next;
t->next=NULL; ////
n++;
}
c1->next=d0.next;
return d1.next;
}
};9.6 237. Delete Node in a Linked List
https://leetcode.com/problems/delete-node-in-a-linked-list
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
9.7 203. Remove Linked List Elements
https://leetcode.com/problems/remove-linked-list-elements/
Use delete the next node algo above:
struct Solution {
ListNode *removeElements(ListNode *head, int val) {
ListNode dummy(0);
dummy.next = head;
head = &dummy; // move head to its previous node(dummy node)
while (head->next)
if (head->next->val == val) head->next = head->next->next;
else head = head->next;
return dummy.next;
}
};or using a previous node:
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode d(0);
d.next=head;
ListNode* c=head, *p=&d;
while(c){
if(c->val==val) p->next=c->next;/*no move for p*/ else p=p->next;
c=c->next;
}
return d.next;
}
};
Be careful it is wrong to use delete the current node algo like below:
struct Solution {
ListNode* removeElements(ListNode* head, int val) {
ListNode d(0);
d.next=head;
while(head){
if(head->val==val){
if(head->next){
head->val=head->next->val, head->next=head->next->next;
}else head=0;
}else head=head->next;
}
return d.next;
}
};It will fail for this case:
Input:[1,2,6,3,4,5,6], 6
Output:[1,2,3,4,5,6]
Expected:[1,2,3,4,5]也可以用递归来解,写法很简洁,通过递归调用到链表末尾,然后回来,需要要删的元素,将链表next指针指向下一个元素即可:
9.8 138. Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
https://leetcode.com/problems/copy-list-with-random-pointer
- Map from old node to new old, and copy twice!
这题的关键是如何track一个节点是否已经被copy了.假如我们要copy如下list,用指针p1来扫描每个节点,另一个指针p2建立copy.
______
| |
| V
1->2->3p1扫描1时,p2复制1,以及1->next (2), 1->random (3).之后p1, p2分别移到各自的2节点.此时我们必须得知道节点3在之前已经被复制了,并且得知道复制节点的地址.
______
| |
| V
1->2->3所以这里可以使用一个hash table来记录原节点和复制节点的地址对应关系.这样每次要建立当前节点p的next和random前,先在hash table中查找.如果找到,则直接连接;否则建立新节点连上,并把和原节点的对应关系存入hash table中.
http://bangbingsyb.blogspot.com/2014/11/leetcode-copy-list-with-random-pointer.html
struct Solution {
map<RandomListNode*, RandomListNode*> m;
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *p = copyNext(head), *c = p;
while (head) {
c->random = m[head->random]; ////!!!!
head = head->next, c = c->next;
}
return p;
}
RandomListNode *copyNext(RandomListNode *head) {
RandomListNode h(0);
RandomListNode* c = &h;// c is node before new head
while (head) {
c->next = new RandomListNode(head->label);
m[head] = c->next;// old -> new
head = head->next, c = c->next;
}
return h.next;
}
};- JAVA
这道题本质是一个Graph traversal问题．下面是DFS的写法.
public class Solution {
private Map<RandomListNode,RandomListNode> visited=new HashMap<>();
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null) return null;
if(visited.containsKey(head)){ return visited.get(head);}
RandomListNode n=new RandomListNode(head.label);
visited.put(head,n);
n.next = copyRandomList(head.next);
n.random = copyRandomList(head.random);
return n;
}
}Simliar Problem: Clone Graph
- No Extra Sapce
http://blog.csdn.net/linhuanmars/article/details/22463599
http://www.cnblogs.com/TenosDoIt/p/3387000.html
http://fisherlei.blogspot.com/2013/11/leetcode-copy-list-with-random-pointer.html
9.9 Merge Two Sorted Lists
Three pointers; https://leetcode.com/problems/merge-two-sorted-lists/
T: \(O(N+M)\), S:\(O(1)\)
9.10 Merge K Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
https://leetcode.com/problems/merge-k-sorted-lists/
The naive way is to scan heads and find min node per scan. This will take O(N*K) time, where \(N\) is the average length of all lists.
http://bangbingsyb.blogspot.com/2014/11/leetcode-merge-k-sorted-lists.html
9.10.1 Priority Queue
T: \(O(NlogK)\), S:\(O(K)\) where N is total number of Nodes and K is number of lists
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0)
return null;
ListNode r= new ListNode(0);
ListNode c= r;
Comparator<ListNode> comp = new Comparator<ListNode>(){
public int compare(ListNode a, ListNode b){
return a.val - b.val;
}
};
Queue<ListNode> q = new PriorityQueue<ListNode>(lists.length, comp);
for(int i=0; i<lists.length; i++){
if(lists[i]!=null)
q.offer(lists[i]);
}
while(!q.isEmpty()){
ListNode top = q.poll();
r.next = top;
if(top.next != null){
q.offer(top.next);
}
r = r.next;
}
return c.next;
}
}Here we construct priority queue by insertion because we are not inserting all nodes.(Only those non-empty nodes.)
9.10.2 mergeTwoLists
T: \(O(NlogK)\), S:\(O(K)\)
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) { return nullptr; }
if (lists.size() == 1) return lists[0];
vector<ListNode*> v;
for (int i = 0; i<lists.size(); i += 2)
v.push_back(i + 1 == lists.size() ? lists[i] : mergeTwoLists(lists[i], lists[i + 1]));
return mergeKLists(v);
}题目是merge k sorted list 我给了heap的做法 分析了复杂度 接下来是如何用parallel的算法来做 一开始我以为是考多线程 后来小哥说不对 就是一个线程 然后我猜了一个分治法 歪打正着 然后分析复杂度 然后小哥又问 对于分治法 如果有k个processor的话复杂度会变成多少 这个地方我分析的有点卡壳 之前从来没联系过多个处理器情况的复杂度分析 然后小哥给了一下提示 做出来了
9.11 141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
9.11.1 Cycle detection
https://leetcode.com/problems/linked-list-cycle
https://en.wikipedia.org/wiki/Cycle_detection
Floyd’s Tortoise and hare 龟兔赛跑算法
https://charleshm.gitbooks.io/leetcode/content/lian_biao_cheng_huan.html
9.12 142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
https://leetcode.com/problems/linked-list-cycle-ii
http://www.cnblogs.com/hiddenfox/p/3408931.html
证明其实没那么简单,网上很多错的误导人的证明(比如说\(a==c\)这显然是不对的,设想\(a\)很大,圈很小!!!). 两个指针相遇前可能已经绕了环N,M圈了.设圈的长度为L
The tortoise moves \(d=a+b+NL\), hare moves two times as tortoise \(2d=a+b+ML\), so \(d=(M-N)L=a+b+NL\), and \(a+b=(M-2N)L\).
\(M-2N\)是一个大于0的integer.
So at point Z, if tortoise moves \(a\) step, it will get point Y.
\(a\)不一定等于\(c\),但是可以保证的是,从Z点出发,再走a步肯定到达Y点(虽然完全可能已经绕了好几个圈!!!).
9.13 457. Circular Array Loop
You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it’s negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be “forward” or "backward’.
Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.
Example 2: Given the array [-1, 2], there is no loop.
Note: The given array is guaranteed to contain no element “0”.
Can you do it in O(n) time complexity and O(1) space complexity?
https://leetcode.com/problems/circular-array-loop/
注意The loop must be “forward” or "backward’. 所以这就是为什么[-2, 1, -1, -2, -2]是false的原因
说实话,这道题描述的并不是很清楚,比如题目中有句话说循环必须是forward或是backward的,如果不给例子说明,不太容易能get到point.所谓的循环必须是一个方向的就是说不能跳到一个数,再反方向跳回来,这不算一个loop.比如[1, -1]就不是一个loop,而[1, 1]是一个正确的loop.看到论坛中一半的帖子都是各种需要clarify和不理解test case就感觉很好笑～博主也成功踩坑了.弄清楚了题意后来考虑如何做,由于从一个位置只能跳到一个别的位置,而不是像图那样一个点可以到多个位置,所以这里我们就可以根据坐标建立一对一的映射,一旦某个达到的坐标已经有映射了,说明环存在,当然我们还需要进行一系列条件判断.首先我们需要一个visited数组,来记录访问过的数字,然后我们遍历原数组,如果当前数字已经访问过了,直接跳过,否则就以当前位置坐标为起始点开始查找,进行while循环,将当前位置在visited数组中标记true,然后计算下一个位置,计算方法是当前位置坐标加上对应的数字,由于是循环数组,所以结果可能会超出数组的长度,所以我们要对数组长度取余.当然上面的数字也可能是负数,加完以后可能也是负数,所以光取余还不够,还得再补上一个n,使其变为正数.此时我们判断,如果next和cur相等,说明此时是一个数字的循环,不符合题意,再有就是检查二者的方向,数字是正数表示forward,若是负数表示backward,在一个loop中必须同正或同负,我们只要让二者相乘,如果结果是负数的话,说明方向不同,直接break掉.此时如果next已经有映射了,说明我们找到了合法的loop,返回true,否则建立一个这样的映射,继续循环.
http://www.cnblogs.com/grandyang/p/7658128.html
class Solution {
public:
bool circularArrayLoop(vector<int>& nums) {
unordered_map<int, int> m;
int n = nums.size();
vector<bool> visited(n, false);
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
int cur = i;
while (true) {
visited[cur] = true;
int next = (cur + nums[cur]) % n;
if (next < 0) next += n;
if (next == cur || nums[next] * nums[cur] < 0) break;
if (m.count(next)) return true;
m[cur] = next;
cur = next;
}
}
return false;
}
};- Simplest way to check if two integers have same sign?
(a ^ b) >= 0- Java
Just think it as finding a loop in Linkedlist, except that loops with only 1 element do not count. Use a slow and fast pointer, slow pointer moves 1 step a time while fast pointer moves 2 steps a time. If there is a loop (fast == slow), we return true, just except there’s only 1 element in the loop. else if we meet element with different directions, then the search fail, we set all elements along the way to 0. Because 0 is fail for sure so when later search meet 0 we know the search will fail.
public class Solution {
int[] arr;
public boolean circularArrayLoop(int[] nums) {
arr = nums;
for (int i=0; i<nums.length; i++) {
if (nums[i] == 0) continue;
//two pointers
int j=i, k=shift(i);
while (nums[i]*nums[k]>0 && nums[i]*nums[shift(k)]>0) {
if (j == k) {
// check for loop with only one element
if (j == shift(j)) break;
return true;
}
j = shift(j);
k = shift(shift(k));
}
// loop not found, set all element along the way to 0
j = i;
int val = nums[i];
while (nums[j]*val > 0) {
int next = shift(j);
nums[j] = 0;
j = next;
}
}
return false;
}
public int shift(int pos) {
return (pos+arr[pos]+arr.length) % arr.length;
}
}9.14 2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. 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.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.https://leetcode.com/problems/add-two-numbers/
这道题已经把数字颠倒过来了,所以就比较简单,直接从头到尾循环了事.
struct Solution {
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int sum=0, carry=0;
ListNode h(0);
ListNode* r=&h;
while(l1 || l2){
sum = (l1?l1->val:0) + (l2?l2->val:0) + carry;
if(sum>=10){sum%=10, carry=1;}else{carry=0;}
r->next = new ListNode(sum); // create new node
r = r->next;
if(l1)l1=l1->next;
if(l2)l2=l2->next;
}
if(carry) r->next=new ListNode(carry);/// 5+5=10
return h.next;
}
};注意考虑5+5这种情况.
如果数字没有颠倒,应该要用recursive搞定. 果然真有一题下面.
9.15 445. Add Two Numbers II
https://leetcode.com/problems/add-two-numbers-ii/
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7仔细想了下直接递归好像还不太容易. 上面的例子递归到最后肯定是3 + NULL,其他例子可能是3->4->5->NULL + NULL,那么返回什么给上一层使用呢? 上一层如果是2->3->4->5->NULL + 1->NULL,1其实应该和5相加,这样就破坏了返回的结果.所以这样递归好像不行.
要不先算出两个list的长度,然后把两个list尾部对齐再递归?这样应该可行!
struct Solution { // 32ms, 81%
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* t=l1;
int len1=0, len2=0;
while(t) len1++, t=t->next;
t=l2;
while(t) len2++, t=t->next;
if (len1<len2) swap(l1,l2); // assume l1 is the longer one
int carry=0;
auto r = rec(l1, l2, abs(len1-len2), carry);
if(carry){auto p=new ListNode(carry); p->next=r; r=p;}
return r;
}
ListNode* rec(ListNode* l, ListNode* r, int d, int& carry){
int sum=0;
if(d){
auto tmp=rec(l->next, r, d-1, carry);
sum += l->val+carry;
carry=sum/10, sum = sum%10;////
auto p = new ListNode(sum);
p->next = tmp;
return p;
}//d==0
if(!l->next && !r->next){ // 递归终止条件
sum = l->val + r->val + carry;
carry=sum/10, sum = sum%10;
return new ListNode(sum);
}
auto t = rec(l->next, r->next, 0, carry);
sum += l->val+r->val+carry;
carry=sum/10, sum = sum%10; ////
auto p = new ListNode(sum);
p->next = t;
return p;
}
};http://www.cnblogs.com/grandyang/p/6216480.html
借助stack的方法很简单.
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2;
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2) {
s2.push(l2->val);
l2 = l2->next;
}
int sum = 0;
ListNode *res = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
if (!s1.empty()) { sum += s1.top(); s1.pop(); }
if (!s2.empty()) { sum += s2.top(); s2.pop(); }
res->val = sum % 10;
ListNode *head = new ListNode(sum / 10);
head->next = res;
res = head;
sum /= 10;
}
return res->val == 0 ? res->next : res;
}
};9.16 306. Additive Number
Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example: “112358” is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
“199100199” is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.
Follow up: How would you handle overflow for very large input integers?
https://leetcode.com/problems/additive-number/
思路: 一个基本的思想就是确定了第一个和第二个数之后, 以后的数就是验证了, 所以只要枚举第一和第二个数, 然后不断验证下面的字符串子串是否是前两个数的和即可. 因为数字可能超出整数的范围, 因此在验证一个数是否是另外两个和的时候, 可以用字符串相加来模拟整数相加. 另外需要注意的是’0’字符, 如果他在子串的首位, 那么他只能以“0”的形式存在.
class Solution {
public:
string getSum(string num1, string num2) {
int val, flag = 0, len1 = num1.size(), len2 = num2.size();
string sum;
while(len1 || len2)
{
int val = 0;
if(len1 > 0) val += num1[len1 -1] - '0', len1--;
if(len2 > 0) val += num2[len2 -1] - '0', len2--;
sum += to_string((val+flag)%10);
flag = (val+flag)/10;
}
if(flag) sum += "1";
reverse(sum.begin(), sum.end());
return sum;
}
bool DFS(string& num1, string& num2, string& num3) {
if(num3.size() ==0) return true;
string sum = getSum(num1, num2);
for(int i = 1; i <= num3.size(); i++)
{
string str = num3.substr(0, i), tem = num3.substr(i);
if(str==sum && DFS(num2, str, tem)) return true;
if(num3[0] == '0') break;
}
return false;
}
bool isAdditiveNumber(string num) {
if(num.size() < 3) return false;
int len = num.size();
for(int i = 1; i <= len-2; i++)
{
string num1=num.substr(0, i);
for(int j = i+1; j <= len-1; j++ )
{
string num2 =num.substr(i, j-i), num3=num.substr(j);
if(DFS(num1, num2, num3)) return true;
if(num[i] == '0') break;
}
if(num[0] == '0') break;
}
return false;
}
}; 9.17 Intersection of 2 Linked Lists
https://leetcode.com/problems/intersection-of-two-linked-lists
Refer to: linkedin-2016-11.html#intersection-of-two-linked-lists
9.18 19. Remove Nth Node From End of List
https://leetcode.com/problems/remove-nth-node-from-end-of-list
struct Solution {
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode d(0);
d.next=head;
ListNode* s=&d, *f=head;//s!=head
while(n--) f=f->next;
while(f)
f=f->next, s=s->next;
s->next=s->next->next; // not s=s->next;
return d.next;
}
};容易出错的地方是s的初始化.因为这里用的删除node的方法至少需要两个节点.
9.19 83. Remove Duplicates from Sorted List
https://leetcode.com/problems/remove-duplicates-from-sorted-list
9.20 82. Remove Duplicates from Sorted List II
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii
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;
}
};9.21 147. Insertion Sort List
https://leetcode.com/problems/insertion-sort-list
struct Solution {
ListNode *insertionSortList(ListNode *head) {
ListNode *dummy = new ListNode(0);
// 这个dummy的作用是,把head开头的链表一个个的插入到dummy开头的链表里
// 所以这里不需要dummy->next = head;
while (head != NULL) {
ListNode *temp = dummy;
ListNode *next = head->next;
while (temp->next != NULL && temp->next->val < head->val) {
temp = temp->next;
}
head->next = temp->next;
temp->next = head;
head = next;
}
return dummy->next;
}
};- JAVA
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode d=new ListNode(0), p=head;
d.next=head;
while(p.next != null){
if(p.val <= p.next.val){
p=p.next;
}else{
ListNode t=p.next, q=d;
p.next=p.next.next;
while(q.next.val < t.val)
q=q.next;
t.next=q.next;
q.next=t;
}
}
return d.next;
}
}9.22 92. Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
https://leetcode.com/problems/reverse-linked-list-ii
struct Solution {
void reverse(ListNode *head) {
ListNode *prev = 0, *temp;
while (head)
temp = head->next, head->next = prev, prev = head, head = temp;
}
ListNode* findkth(ListNode *head, int k) {
while(k--)
if ((head = head->next) == NULL) return NULL;
return head;
}
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode *dummy = new ListNode(0);
dummy->next=head;
ListNode *mth_prev = findkth(dummy, m - 1);
ListNode *mth = mth_prev->next;
ListNode *nth = findkth(dummy, n);
ListNode *nth_next = nth->next;
nth->next = 0;
reverse(mth);
mth_prev->next = nth;
mth->next = nth_next;
return dummy->next;
}
};9.23 382. Linked List Random Node
Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.
Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
https://leetcode.com/problems/linked-list-random-node/
Reservoir Sampling
9.24 61. Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
Example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.https://leetcode.com/problems/rotate-list/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL) { return NULL; }
int n = 1;
ListNode* lastOne = head;
while (lastOne->next != NULL) {
n++;
lastOne = lastOne->next;
}
if (n == k) { return head; }
int firstNum = n - (k % n);
ListNode* newLastOne;
newLastOne = head;
for (int i = 1; i < firstNum; i++)
newLastOne = newLastOne->next;
lastOne->next = head;
head = newLastOne->next;
newLastOne->next = NULL;
return head;
}
};9.25 82. 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.
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
http://www.cnblogs.com/springfor/p/3862077.html
http://blog.csdn.net/wcx909241523/article/details/77725671
https://www.awesomescreenshot.com/showImage?img_id=3165370
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode d = new ListNode(0);
d.next = head;
ListNode c = d;
ListNode slow = d.next;
ListNode fast = d.next.next;
boolean flag = false;
while(fast!=null){
if(slow.val == fast.val){
flag = true;
fast = fast.next;
if(fast == null)
c.next = null;
}else{
if(flag){
c.next = fast;
flag = false;
}else{
c = slow;
}
slow = fast;
fast = fast.next;
}
}
return d.next;
}Recursion rocks:
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
int val = head->val;
ListNode* n = head->next;
if (n->val != val) {
head->next = deleteDuplicates(n);
return head;
} else {
while (n && n->val == val) n = n->next;
return deleteDuplicates(n);
}
}
};