| Intersection of Two Linked Lists | 28.9% | |||
| Sort List | 2013-11-16 | 20.8% | Medium | |
| Insertion Sort List | 2013-11-12 | 25.4% | Medium | |
| Reorder List | 2013-11-02 | 20.5% | Medium | |
| Linked List Cycle II | 2013-10-30 | 30.8% | Medium | |
| Linked List Cycle | 2013-10-28 | 35.9% | Medium | |
| Copy List with Random Pointer | 2013-10-03 | 23.6% | Hard | |
| Flatten Binary Tree to Linked List | 2012-10-14 | 28.2% | Medium | |
| Convert Sorted List to Binary Search Tree | 2012-10-02 | 27.4% | Medium | |
| Reverse Linked List II | 2012-06-27 | 26.1% | Medium | |
| Partition List | 2012-04-30 | 27.0% | Medium | |
| Remove Duplicates from Sorted List II | 2012-04-22 | 24.8% | Medium | |
| Remove Duplicates from Sorted List | 2012-04-22 | 34.6% | Easy | |
| Merge Two Sorted Lists | 2012-03-30 | 33.1% | Easy | |
| Rotate List | 2012-03-27 | 21.9% | Medium | |
| Merge k Sorted Lists | 2012-02-13 | 21.0% | Hard | |
| Remove Nth Node From End of List | 2012-01-27 | 28.9% | Easy |
Intersection of Two Linked Lists
两种情况： 存在交点，不存在（null）
先统计len1，len2. 然后判断最后一个节点的地址是否相等。不是则不存在，回null。是则先让长的走过delta步长，再同时走，直到到达相同地址，返回之。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode * p=headA, *pp=NULL, *q=headB, *pq=NULL, *tmp;
int i = 0; while(p) i++, pp = p, p=p->next;
int j = 0; while(q) j++, pq = q, q=q->next;
if(pp!=pq) return NULL;
if(i<j) tmp = headA, headA = headB, headB = tmp;
for(int k = 0; k<abs(i-j); k++) headA=headA->next;
while(headA!=headB) headA=headA->next, headB=headB->next;
return headA;
}
};
sort list
链表与二分法结合在一起。注意区间运算，尤其是mid。
20‘ ac 归并排序
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(!head) return head;
return sort(head, NULL);
}
ListNode* sort(ListNode *l, ListNode *r){
// assert(l != NULL);
if( l ->next == r ) {
l->next = NULL;
return l;
}
ListNode *p=l, *p2=l;
while(p2 != r && p2->next != r){
p=p->next; p2=p2->next->next;
}
ListNode *a, *b, *head = NULL, *tail = NULL;
a = sort(l, p);
b = sort(p, r);
while(a != NULL && b != NULL ){
if( a->val > b->val ) {ListNode *tmp = a; a = b; b = tmp; }//@error
if(!head) head = a;
if(tail) tail -> next = a;
tail = a;
a=a->next;
}
if( a!= NULL ){
if(!head) head = a;
if(tail) tail -> next = a;
}
if( b!= NULL){
if(!head) head = b;
if(tail) tail -> next = b;
}
return head;
}
};
上述代码要注意
while(p2!=r && p2->next!=r){
p=p->next; p2=p2->next->next;
}
这里p = mid 指向了中点(l+r)/2，注意r是不包括在内的，而 p2 指向了左闭右开 【l, r) 区间的最后一个元素，或者r。注意如果把【l，r）改写成全闭区间【L,R], 那么上面的运算的结果mid=( L + R+1)/2。总之mid实际上是中间偏右的一个点，不是纯正的中点。
在此基础上，就可以二分成： sort(l, r) => sort(l, p), sort(p, r) （[l, r) => [l, (l+r)/2), [(l+r)/2, r) )
上述代码还可以优化： 对于当前链表<head, tail>,向后链入元素a，只需要以下三句：
if(!head) head = a; else tail -> next = a; tail = a;
是不是逻辑很清晰？
我们就把上面三句话构成的append方法叫做 head-tail-append吧。
基数排序
上题也可以基数排序，毕竟保存的都是数嘛。注意弄19个链表<lists[i], tails[i]>；
从个位往高位依次排序，重复下面过程：
- 遍历<lst, tail>中的节点it，append该节点到该位（-9 ~ 9）对应的链表<lists[i], tails[i]> 中；
- 置<lst, tail> 为<NULL, xx>，即清空。
- 从9到-9依次把<lists[i], tails[i]>append到<lst, tail> 中。
- 置<lists[i], tails[i]>为<NULL, xx>，即清空。
下面是非常漂亮的一段实现代码。
ListNode *sortList(ListNode *head) {
ListNode* lsts[19];//-9~9
ListNode* tails[19];
typedef ListNode* PNode;
ListNode* lst=head,*tail;
if(lst==NULL) return NULL;
//基数排序
int d=1;
while(d<0xfffffff){
for(int i=0;i<19;i++) lsts[i]=NULL;
for(PNode it=lst;it!=NULL;it=it->next){
int s=9+(it->val/d)%10;//0~18
// head-tail-append 三句代码,append 节点it
if(!lsts[s]) lsts[s]=it;
else tails[s]->next=it;
tails[s]=it;
}
lst=NULL; // <lst, tail> inited as <NULL, xx>
for(int i=0;i<19;i++){
if(lsts[i]){
// head-tail-append 三句代码再次出现
if(!lst) lst=lsts[i],tail=tails[i];
else tail->next=lsts[i],tail=tails[i];
}
}
tail->next=NULL;
d*=10;
}
return lst;
}
把链表转成平衡二叉树
步骤和上面类似：
1 二分 dfs(l, r):
- 如果 l==r， 空区间 返回NULL
- 如果 l->next == r， 返回一个节点
- 否则 找 mid ，以mid为根节点， 二分为 dfs(l, mid), dfs(mid->next ,r)
寻找mid的方法（下面方法找到的mid偏右）
p1 = l, p2 = l;
while(p2 !=r && p2->next !=r){
p1 = p1->next, p2 = p2->next->next;
} //p1 将指向[l, r) 中的(l+r)/2
//一定要记得二分法中mid=(l+r)/2的含义：
// 示意图：# # * # #, 或者 # * #
// 区间对应[l, r] 或 [l, r)
TreeNode *convert(ListNode *l, ListNode *r){
if(l == r) return NULL;
if(r == l->next) return new TreeNode(l->val);
ListNode *mid=l, *p2 = l;
while(p2 != r && p2->next != r){
mid = mid->next, p2 = p2->next->next;
}
TreeNode *lt = convert(l, mid), *rt = convert(mid->next, r);
TreeNode *p = new TreeNode(mid->val);
p->left = lt, p->right = rt;
return p;
}
或者用计数法找中点mid，则n=区间节点个数，区间[0, n-1]的中点mid的下标为( 0 + n-1 ) / 2, 用 pm = left; for(i=0; i<mid; i++) pm = pm->next;即可得到中央节点pm
TreeNode *dfs(ListNode *left,int n){
if(n<=0) return NULL;
ListNode *mid=left;
for(int i=0;i<(n-1)/2;i++) mid=mid->next;
TreeNode *node=new TreeNode(mid->val);
TreeNode *pl=dfs(left,(n-1)/2),*pr=dfs(mid->next,n/2);
node->left=pl,node->right=pr;
return node;
}
删除倒数第k个节点
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode *p=head,*pre = NULL, *q = head;
int i = 1; for(; i<n && q; i++) q = q->next;
if(i==n){
while(q->next) pre = p, p = p->next, q = q->next;
if(!pre){
head = head -> next;
}
else pre->next = pre->next->next;
free(p);
}
return head;
}
};
或者
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode *p=head,*pre;
int i;for(i=0;p!=NULL;i++){ p=p->next;} //i=size
if(n>i||n<=0) return head;
n=i-n; //point[n]
pre=head;
for(i=0;i<n-1;i++) pre=pre->next;
if(n-1<0) {head=head->next; return head;}
pre->next=pre->next->next;
return head;
}
};
划分List （小于x | 大于等于x）
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *p=head,*pre=NULL;
while(p!=NULL&&p->val<x){ pre=p,p=p->next;}
if(p!=NULL){//p->val>=x
ListNode *q=p->next,*preq=p;
while(q!=NULL){
if(q->val<x){
//cut q and insert before p
preq->next=q->next;
if(pre!=NULL) {pre->next=q;}
else {head=q;}//head change
q->next=p;
pre=q;
}
preq=q,q=q->next;//@attention: not good
}
}
return head;
}
};
或者
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode * p = head, *pp = NULL;
while(p && p->val < x) pp = p, p = p->next;
if(p){
ListNode * q = p->next, * pq = p;
while(q){
if( q->val < x )
{
pq -> next = pq->next->next;
if(!pp) head = q;
else pp -> next = q;
pp = q;
pp -> next = p;
q = pq -> next;//@important
}
else pq = q, q = q->next;
}
}
return head;
}
};
copy list with random pointer
整体上分为三步骤：
第一步对每个节点拷贝一个新的跟在后面，
第二步非常重要：在这里而不是在后面修改新节点的random指针，并且注意“空指针”
第三步，拆分原有链表和新增链表（用p1,q1分别表示新增表头尾指针即可）。用到了上述的head-tail-append三句代码。
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode * p = head, *np;
while(p){
RandomListNode * t = new RandomListNode(p->label);
t->random = p->random;
t->next = p->next;
p->next = t;
p = t->next;
}
//@error: should change random below, not later
p = head;
while(p){
np = p->next;
if(np->random) np->random = np->random->next;
p = np->next;
}
p = head;
RandomListNode *p1=NULL, *q1;
while(p){
np = p->next;
// if(np->random) np -> random = np->random->next; //@error: should be changed earlier
if(p1) q1->next = np;
else p1 = np;
q1 = np;
p -> next = np->next;
p = p -> next;
}
return p1;
}
};
链表插入排序
链表插入排序用到了 链表的遍历 和 插入（区分头插入和中间插入），
步骤：
1 <head, .... NULL> 为已经排序的部分， 初始化为<head, NULL>
<p, ...NULL> 为待插入的部分，初始化为<head->next, NULL>
2 每次在<head,.. .NULL> 中寻找p的插入点<pre, q=pre->next>,
- 将p->next 置为NULL，准备插入（此外np记录下一个p）
- 如果pre==NULL，说明q=head, p将插入到<head, NULL>之前，于是头部插入， p替代head （p->next=head, head=p;)
- 否则， 在<head, NULL> 中间或末尾插入，如果在末尾则q为NULL （pre->next = p, p->next = q; )
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if(!head) return head;
ListNode *q =NULL, *pre = NULL, *p = head->next, *np;
head -> next = NULL;
while(p){
np = p->next;
p->next = NULL; // cut p
pre = NULL, q = head;
while(q && q->val <= p->val) pre = q, q = q->next;
if(!pre) p->next = head, head = p;
else p -> next = pre -> next, pre->next = p;
p = np;
}
return head;
}
};
Reorder List
只想到了O（n）空间复杂度的解法。有O（1）空间的解法吗？
void reorderList(ListNode *head) {
if(!head) return;
vector<ListNode *> vec;
ListNode * p =head;
while(p) vec.push_back(p), p = p->next;
int n = vec.size();
for(int i = 0; i<=(n-1)/2; i++){
if(i>0) vec[n-i]->next = vec[i];
vec[i]->next = vec[n-1-i];
vec[n-1-i]->next = NULL;
}
}
Remove Duplicate 2
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
ListNode * pre = NULL, * p = head, *np;
head = NULL; // <head, pre> inited to <NULL, xx>
while(p){
ListNode * q = p->next, *tmp;
while(q && q->val == p->val) q = q->next;
// append p to <head, pre>
if(q==p->next){
p->next = NULL;
if(!pre) head = p;
else pre->next = p;
pre = p;
}
//skip duplicated p
else{
while(p!=q) {
ListNode *tmp = p->next;
free(p);
p = tmp;
}
}
//next p
p = q;
}
return head;
}
};
或者
保持左边<head, pre>和右边的p的链接。
ListNode *deleteDuplicates(ListNode *head) {
ListNode *p=head,*pre=NULL;
while(p!=NULL&&p->next!=NULL){
if(p->val==p->next->val){
int val=p->val; ListNode *next;
while(p!=NULL&&p->val==val){
next=p->next;
delete p;
p=next;
}
// <head, pre> link to next p
if(pre!=NULL) pre->next=p;
else { head=p; }
}
else{
// p append to <head, pre>
pre=p,p=p->next;
}
}
return head;
}
};
swap pairs
注意np，pp分别代表什么
ListNode *swapPairs(ListNode *head) {
ListNode * p = head, *q = p, *np, *pp = NULL;
while(p && p->next){
np = p->next->next;
q = p->next;
q -> next = p;
// link last section with q
if(pp) pp -> next = q;
// first section, then head change
else head = q;
pp = p, p = np;
}
// link last section with p=NULL or single element
if(pp) pp->next = p;
return head;
}
rotate list
这个题目比较坑爹的地方在于k的大小可以超过n，
记得shift k相当于把下标为（n-k%n)%n的元素给作为首节点，就OK了
ListNode *rotateRight(ListNode *head, int k) {
int n =0;
ListNode * p = head, * pre = NULL, *tail = NULL;
while(p){ n++; tail = p, p = p->next; }
if(n==0) return head;
k = (n - k%n)%n;
if(k==0) return head;
p = head;
for(int i=0; i<k; i++){ pre = p, p = p->next; }
tail -> next = head, head = p, pre -> next = NULL;
return head;
}
add two numbers
非常优美的，从第一个节点汪最后一个节点计算和append：
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
// @error: no need to reverse l1 or l2
/*ListNode * p = l2, *pp =NULL;
while(p){
ListNode *np = p->next;
p->next = pp;
pp = p, p = np;
}
l2 = pp;*/
ListNode * l3 = NULL, *tail;//head
int c =0;
while(l1 || l2 || c){
int a= l1? l1->val:0;
int b = l2? l2->val:0;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
int t = a + b + c;
if(t>=10) t%=10, c=1;
else c = 0;
ListNode * tmp = new ListNode(t);
//tmp->next = l3, l3 = tmp; //@error: should not insert in the head of <l3, xx>, because head is the lowest bit
if(!l3) l3 = tmp; //@attention: should append tmp to <l3, tail>
else tail->next = tmp;
tail = tmp;
}
return l3;
}