简单题
21. 合并两个有序链表（无题解）
23. 合并K个升序链表（无题解）
148. 排序链表（无题解）
234. 回文链表（无题解）
剑指 Offer 24. 反转链表（无题解）
剑指 Offer 18. 删除链表的节点（无题解）
面试题 02.02. 返回倒数第 k 个节点（无题解）
876. 链表的中间结点（无题解）
面试题 17.12. BiNode
面试题 02.01. 移除重复节点
中等题
2. 两数相加
86. 分隔链表
114. 二叉树展开为链表
面试题 02.05. 链表求和
难题
138. 复制带随机指针的链表
147. 对链表进行插入排序
328. 奇偶链表
题解
面试题 17.12. BiNode
struct TreeNode* hash[100010];int hashsize = 0; void visit(struct TreeNode * root){ if(root){ if(root->left) visit(root->left); hash[hashsize++] = root; if(root->right) visit(root->right); } } struct TreeNode* convertBiNode(struct TreeNode* root){ hashsize = 0; visit(root); for(int i = 0;i < hashsize - 1;i++){ hash[i]->left =0; hash[i]->right = hash[i+1]; } if(!hashsize) return NULL; hash[hashsize - 1]->left = 0; hash[hashsize - 1]->right = 0; return hash[0]; }
面试题 02.01. 移除重复节点
struct ListNode* removeDuplicateNodes(struct ListNode* head){ int hash[20001]; memset(hash,0,sizeof(hash)); struct ListNode anshead; anshead.next = head;head = &anshead;//头节点 while(head->next){ if(!hash[head->next->val]){ hash[head->next->val] ++; head = head->next; } else{ head ->next= head->next->next; } } return anshead.next; }
2. 两数相加
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ int jinwei = 0; struct ListNode *head = malloc(sizeof(struct ListNode)); struct ListNode *ans = head;//很多地方用头节点很省事 就 很省事？ head->next = 0; //创建头节点 while(l1&&l2){ ans->next = malloc(sizeof(struct ListNode)); //创建节点 ans = ans->next; ans->val = (l1->val + l2->val + jinwei) % 10;//创建信息 jinwei = (l1->val + l2->val + jinwei) / 10; l1=l1->next; l2=l2->next; } while(l1){ //处理l1剩余 ans->next = malloc(sizeof(struct ListNode)); //创建节点 ans = ans->next; ans->val = (l1->val + jinwei) % 10;//创建信息 jinwei = (l1->val + jinwei) / 10; l1=l1->next; } while(l2){ //处理l2剩余 ans->next = malloc(sizeof(struct ListNode)); //创建节点 ans = ans->next; ans->val = (l2->val + jinwei) % 10;//创建信息 jinwei = (l2->val + jinwei) / 10; l2=l2->next; } while(jinwei){ //处理进位剩余 ans->next = malloc(sizeof(struct ListNode)); //创建节点 ans = ans->next; ans->val = jinwei % 10; jinwei/= 10; } ans->next = 0; return head->next; }
86. 分隔链表
struct ListNode* partition(struct ListNode* head, int x){ struct ListNode *small = malloc(sizeof(struct ListNode)),*p = small;//两个链表分别执行尾插 struct ListNode *big = malloc(sizeof(struct ListNode)),*q = big; big->next = 0;//为了处理空串 //根据元素进行插入 while(head){ if(head->val < x){ p->next = head; p = p->next; } else{ q->next = head; q = q->next; } head = head->next; } //链接链表 p->next = big->next; q->next = 0; return small->next; }
114. 二叉树展开为链表
struct TreeNode *zhan[4090];//保存先序遍历的顺序 int zhansize = 0; void first_root(struct TreeNode * root){ if(root){ zhan[zhansize++] = root; if(root->left) first_root(root->left); if(root->right) first_root(root->right); } } void flatten(struct TreeNode* root){ first_root(root); int i; for(i = 0;i <zhansize - 1;i++){ zhan[i]->left = 0; zhan[i]->right = zhan[i + 1]; } if(!zhansize) return; zhan[i]->left = 0; zhan[i]->right = 0; return; }
面试题 02.05. 链表求和
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ struct ListNode head,*p=&head; int jinwei = 0; while(l1&&l2){ struct ListNode *q = malloc(sizeof(struct ListNode)); q->val = (l1->val + l2->val +jinwei) % 10; jinwei = (l1->val + l2->val +jinwei) / 10; p->next = q; p = q; l1 = l1->next; l2 = l2->next; } while(l1){ struct ListNode *q = malloc(sizeof(struct ListNode)); q->val = (l1->val +jinwei) % 10; jinwei = (l1->val +jinwei) / 10; p->next = q; p = q; l1 = l1->next; } while(l2){ struct ListNode *q = malloc(sizeof(struct ListNode)); q->val = (l2->val +jinwei) % 10; jinwei = (l2->val +jinwei) / 10; p->next = q; p = q; l2 = l2->next; } while(jinwei){ struct ListNode *q = malloc(sizeof(struct ListNode)); q->val = (jinwei) % 10; jinwei /= 10; p->next = q; p = q; } p->next = 0; return head.next; }
138. 复制带随机指针的链表
struct Node* copyRandomList(struct Node* head) { if(!head) return head; struct Node * q = head; while(q){ //在每个head节点后面复制一个相同的链表 struct Node *p = malloc(sizeof(struct Node)); p->val = q->val; p->next = q->next; q->next = p; q = p->next; } q = head; while(q){ //复制random的指向 因为每个对应节点都在原节点后面 if(q->random) q->next->random = q->random->next; else q->next->random = 0; q = q->next->next; } q = head->next; //拆分出结果 while(q->next){ q ->next = q->next->next; q = q->next; } return head->next; }
147. 对链表进行插入排序
struct ListNode* insertionSortList(struct ListNode* head){ if(!head->next||!head) return head; struct ListNode *p = head->next; struct ListNode anshead;//头指针 反正不返回 就在栈区把~~ anshead.next = head; //头指针便于插入 head = &anshead; head->next->next = NULL; //分表 while(p){ struct ListNode *q = head,*temp = p->next; while(q->next && q->next->val < p->val) q = q->next; p->next = q->next; q->next = p; p = temp; } return head->next; }
328. 奇偶链表
struct ListNode* oddEvenList(struct ListNode* head){ struct ListNode *p=0,*q=0,*ji=0,*ou=0; int flag = 0,count = 0; while(head){ //遍历链表 if(count&1){ //奇数 if(!flag) flag = 1; if(!ji) ji = head,p = ji; else p->next = head,p = head; } else { if(!flag) flag = 2; if(!ou) ou = head,q = ou; else q->next = head,q = head; } count ++; head = head->next; } if(flag == 1) { //链接 p->next = ou; if(ou) q->next = 0; return ji; } else if(flag == 2){ //连接 q->next = ji; if(ji) p->next = 0; return ou; } else return 0; //空串 }
