【2】Add Two Numbers (2018年11月30日，第一次review，ko)
两个链表，代表两个整数的逆序，返回一个链表，代表两个整数相加和的逆序。
Example:
Input: ( -> -> ) + ( -> -> )
Output: -> ->
Explanation: + = .
/**
* 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) {
if (!l1 || !l2) {
return l1 == nullptr ? l2 : l1;
}
ListNode *h1 = l1, *h2 = l2;
ListNode *head = , *tail = ;
int carry = ;
while (h1 && h2) {
int num = h1->val + h2->val + carry;
carry = num / , num %= ;
ListNode* node = new ListNode(num);
if (!head) {
tail = head = node;
} else {
tail = tail->next = node;
}
h1 = h1->next, h2 = h2->next;
}
while (h1) {
int num = h1->val + carry;
carry = num / , num %= ;
ListNode* node = new ListNode(num);
tail = tail->next = node;
h1 = h1->next;
}
while (h2) {
int num = h2->val + carry;
carry = num / , num %= ;
ListNode* node = new ListNode(num);
tail = tail->next = node;
h2 = h2->next;
}
if (carry) {
ListNode* node = new ListNode(carry);
carry = ;
tail = tail->next = node;
}
return head;
}
};
【19】Remove Nth Node From End of List （2018年10月30日 算法群）
给了一个链表，从尾部删除第 N 个结点。
题解：two pointers，fast 先走 N 步，然后slow，fast 一起走，fast走到最后一个非空结点，slow就走到了要删除结点的前一个结点。（注意有个特判情况是如果第N个结点是头节点，那么要特殊处理）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head) {return head;}
ListNode *fast = head, *slow = head;
//1. fast goes n steps first
for (int k = ; k < n && fast; ++k) {
fast = fast->next;
}
//2. both slow and fast move simultaneously until fast to the end of the list
if (fast) {
while (fast->next) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
} else {
head = head->next;
}
return head;
}
};
【21】Merge Two Sorted 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) {
if (!l1) {return l2;}
if (!l2) {return l1;}
ListNode *p1 = l1, *p2 = l2, *head = , *tail = ;
while (p1 && p2) {
if (p1->val < p2->val) {
if(!head) {
tail = head = p1;
} else {
tail = tail->next = p1;
}
p1 = p1->next;
} else {
if (!head) {
tail = head = p2;
} else {
tail = tail->next = p2;
}
p2 = p2->next;
}
}
//这里其实不用遍历了，直接连起来ok
if (p1) {
tail->next = p1;
}
if (p2) {
tail->next = p2;
}
return head;
}
};
【23】Merge k Sorted Lists
给了k个已经排好序的链表，要返回一个综合排序的大链表（归并排序）
题解：用 prioprity_queue 的运算符()重载来实现比较函数。具体运算符重载的实现方法见代码。（奇怪的是为啥pq的cmp函数要写 > ，pq里面才是从小到大排序？）
这个题目其实应该复习 priority_queue 的比较函数的实现方法。（要搞懂原理。）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//好奇怪，为啥这里要写大于符号，pq才是从小到大排序... ????
struct cmp{
bool operator() (const ListNode* node1, const ListNode* node2) {
return node1->val > node2->val;
}
}; ListNode* mergeKLists(vector<ListNode*>& lists) {
const int n = lists.size();
if (n == ) {return NULL;}
vector<ListNode*> ptr(n, NULL);
for (int i = ; i < n; ++i) {
ptr[i] = lists[i];
}
ListNode *head = , *tail = ;
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
for (int i = ; i < n; ++i) {
if (!ptr[i]) {continue;} //注意这里有可能有的链表头节点为空，要特判
pq.push(ptr[i]);
ptr[i] = ptr[i]->next;
}
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
if (node->next) { pq.push(node->next); }
if (!head) {
tail = head = node;
} else {
tail = tail->next = node;
}
}
return head;
}
};
【24】Swap Nodes in Pairs （2018年12月1日，第一次复习，没有ko，需要再次复习）
给了一个链表，交换两个相邻的元素。
Given 1->2->3->4, you should return the list as 2->1->4->3.
/**
* 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) {
if (!head) {return head;}
ListNode* pre = , *cur1 = head, *cur2 = cur1->next, *ne = ;
ListNode* h1 = ;
while (cur2) {
ne = cur2->next;
cur2->next = cur1;
cur1->next = ne;
pre = cur1;
if (!h1) {h1 = cur2;}
cur1 = ne;
cur2 = cur1 == nullptr ? nullptr : cur1->next;
pre->next = cur2 == nullptr ? cur1 : cur2;
}
return h1 == nullptr ? head : h1;
}
};
【25】Reverse Nodes in k-Group （）
【61】Rotate List （2018年12月1日，第一次复习，ko，注意边界条件，k = 0 的情况特判）
把一个单链表循环左移k个单位，返回新链表。
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
题解：先走到要左移的第k个结点的前面一个结点，这个结点就是尾部结点，然后把下一个结点当作头结点，做几个指针的赋值操作。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
//1. 先求长度
int len = getLen(head);
if (len == || k ==) {return head;}
if (k >= len) { k %= len; }
if (k == ) {return head;}
//2. 计算应该往前走几步
int step = len - k -;
ListNode* cur = head;
for (int i = ; i < step; ++i) {
cur = cur->next;
}
//3. 标记头尾指针。尾指针就是走了step步的结点cur，头指针是cur的next结点。
ListNode* tail = cur, *h1 = cur->next;
tail->next = ;
cur = h1;
while (cur->next) {
cur = cur->next;
}
cur->next = head;
return h1;
}
int getLen(ListNode* head) {
int ret = ;
ListNode* cur = head;
while (cur) {
ret++;
cur = cur->next;
}
return ret;
}
};
【82】Remove Duplicates from Sorted List II （2018年12月1日，第一次复习，有边界没有想到）
删除一个链表里面的重复结点，（重复结点不保留），返回头结点。
题解：用一个cnt变量记录当前结点出现了几次，如果只出现一次就把在加上。有个小的解题点需要注意，就是如果输入是 [1,2,2] 这种的话，最后的尾结点不是最后的结点这种，每次都要执行 tail->next = 0，来避免这种case。
/**
* 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 *h1 = , *tail = ;
ListNode *pre = head, *cur = head;
while (pre) {
cur = pre->next;
int cnt = ; //用一个变量标记当前结点有几个重复的
while (pre && cur && pre->val == cur->val) {
cur = cur->next;
++cnt;
}
if (cnt == ) {
if (!h1) {
tail = h1 = pre;
} else {
tail = tail->next = pre;
}
tail->next = ; //如果当前结点后面有一堆重复的数的话，那么其实当前结点就是尾结点 [1,2,2]
}
if (cur) {
pre = cur;
} else {
pre = ;
}
}
return h1;
}
};
【83】Remove Duplicates from Sorted List （2018年12月1日，第一次复习，ko）
删除一个链表里面的重复结点（重复结点保留一个，目标是所有结点distinct），返回头结点。
题解：用两根指针遍历，pre指针保存第一次出现的当前元素，cur指针一直往后遍历，直到下一个第一次出现的元素。
/**
* 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 *h1 = head;
ListNode *pre = head, *cur = head, *ne = ;
while (cur) {
cur = cur->next;
while (pre && cur && pre->val == cur->val) {
cur = cur->next;
}
pre->next = cur;
pre = cur;
}
return h1;
}
};
【86】Partition List （2018年12月1日，第一次复习，写的有bug，需要二次复习）
把单向链表按给定的值 x 划分成小于x的结点在左边，大于等于 x 的结点在右边的样子。
题解：（类似题）把一个数组按照给定的值 x 划分成左边小，中间相等，右边大的样子。（这个题叫做荷兰国旗问题，也是快速排序的 partition）。
说回这道题，我先把链表拆成两个，一个是小于 x 的值的链表，一个是大于等于 x 值的链表（拆的时候注意执行 tail->next = 0 的时候，下一个结点一定要用指针提前标记起来，不然下一个结点就丢了）。然后把这两个连接起来就ok了。
/**
* 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) {
vector<ListNode*> h(, nullptr);
vector<ListNode*> tail(, nullptr);
ListNode* cur = head, *ne = ;
while (cur) {
ne = cur->next; //先用一个指针标记下一个结点，不然执行 tail[i]->next = 0 的时候相当于 cur->next = 0。
if (cur->val < x) {
if (!h[]) {
tail[] = h[] = cur;
} else {
tail[] = tail[]->next = cur;
}
tail[]->next = ;
} else {
if (!h[]) {
tail[] = h[] = cur;
} else {
tail[] = tail[]->next = cur;
}
tail[]->next = ;
}
cur = ne;
}
ListNode* ret = , *t = ;
for (int i = ; i < ; ++i) {
if (!h[i]) {continue;}
if (!ret) {
ret = h[i];
t = tail[i];
} else {
t->next = h[i];
t = tail[i];
}
}
return ret;
}
};
【92】Reverse Linked List II （2018年12月1日，第一次复习，需要调试）
把单链表上的第 m 个结点到第 n 个结点这一部分进行反转，m，n是整数，1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
题解：本题需要分类其实，我一开始只想了最普通那种，当 m 不等于 1 的时候，这个时候相当于我先走了 m-1 步，用一个指针标记第 m 个结点的前一个结点，然后从第 m 个结点开始反转 k 个结点（k = n-m+1）。
然而当 m =1 的时候相当于反转整个链表，需要分类处理。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
const int k = n - m + ;
ListNode* newHead = ;
if (m == ) {
newHead = reverse(&head, k);
} else {
ListNode* cur = head;
for (int i = ; i < m-; ++i) {
cur = cur->next;
}
ListNode* pre = cur;
pre->next = reverse(&cur->next, k);
newHead = head;
}
return newHead;
}
ListNode* reverse(ListNode** head, const int k) {
ListNode *pre = , * cur = *head, * ne = ;
ListNode *tail = ;
for (int i = ; i < k && cur; ++i) {
ne = cur->next;
cur->next = pre;
pre = cur;
if (!tail) {tail = cur;}
cur = ne;
}
tail->next = cur;
return pre;
} };
【109】Convert Sorted List to Binary Search Tree （2018年12月1日，第一次复习，WA了一次）
把一个有序的链表拍成一棵高度平衡的二叉树。
Example:
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
题解：我们先用快慢指针找到链表中间的结点，（如果是奇数个结点就指向中心的结点，如果是偶数个结点就指向中间两个结点中靠后的那个结点，这样生成的左子树可能比右子树高度多1）。然后把中间结点当作根结点。递归生成左右子树。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (!head) {return nullptr;}
ListNode* slow = head, *fast = head;
ListNode* pre = ;
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
TreeNode* root = new TreeNode(slow->val);
if (pre) {pre->next = ;}
if (pre != ) { //如果只有单个结点的话，再次调用生成左子树没有任何意义。
root->left = sortedListToBST(head);
}
root->right = sortedListToBST(slow->next);
return root;
}
};
【138】Copy List with Random Pointer （2018年12月1日，第一次复习）
复制含有随机指针结点的链表。一种特殊的链表结点类描述如下：
//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) {}
};
rand指针是ListNode类中新增的指针，这个指针可能指向整个链表中的任何一个结点，也可能指向 null， 给定有这种种类的节点组成的链表头部，请完成该链表的拷贝。
题解：解法一：可以用 map 标记。类似于这种结构 ({1 -> 1'}, {2 -> 2'}, {3->3'})。
解法二：把新拷贝的结点放在原始结点的后面，就是类似于 1 -> 1' -> 2 -> 2' -> 3 -> 3'。然后把 rand 指针串好。在把新旧链表分离出来（本题就要求原来链表出去的时候不能被改变）。
/**
* 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) {
if (!head) {return head;}
//1. copy list without rand ptr
RandomListNode *cur = head, *ne = ;
while (cur) {
ne = cur->next;
RandomListNode* node = new RandomListNode(cur->label);
cur->next = node;
node->next = ne;
cur = ne;
}
//2. copy rand ptr
cur = head, ne = ;
while (cur) {
ne = cur->next->next;
if (cur->random) {
cur->next->random = cur->random->next;
}
cur = ne;
}
//3. split listnode, should recover ori listnode
cur = head;
RandomListNode* h1 = , *t1 = ;
RandomListNode* h2 = , *t2 = ;
while (cur) {
ne = cur->next->next;
if (!h1 && !h2) {
t1 = h1 = cur->next;
t2 = h2 = cur;
} else {
t1 = t1->next = cur->next;
t2 = t2->next = cur;
}
t1->next = ;
t2->next = ;
cur = ne;
}
head = h2;
return h1;
}
};
【141】Linked List Cycle (2019年2月20日)
判断一个linkedlist是不是有环。
题解：快慢指针。如果快慢指针能够相遇，就是有环。否则没有。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head) {return false;}
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
};
【142】Linked List Cycle II （2019年2月20日）
判断一个linkedlist是不是有环，如果有环的话，返回环的起点。
题解：算法是先让快慢指针相遇，相遇之后慢指针回到头结点，然后两根指针同时走一步，再次相遇就是环的起点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//算法是先让快慢指针相遇，相遇之后慢指针回到头结点，然后两根指针同时走一步，再次相遇就是环的起点。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (!head) {return nullptr;}
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
【143】Reorder List (2018年12月1日，第一次review，ko)
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
题解：先按照快慢指针拆分成两个链表，reverse 后面半个链表，然后再拼起来。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if (!head) {return;}
ListNode* slow = head, *fast = head, *pre = ;
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
if (fast && !fast->next) { //奇数个结点
pre = slow;
slow = slow->next;
}
pre->next = ;
ListNode* cur2 = reverse(slow), *cur1 = head;
if (!cur2) {return;} //只有一个结点
ListNode *h1 = , *t1 = ;
while (cur1 && cur2) {
if (!h1) {
t1 = h1 = cur1;
cur1= cur1->next;
} else {
t1 = t1->next = cur1;
cur1 = cur1->next;
}
t1 = t1->next = cur2;
cur2 = cur2->next;
}
if (cur1) {
t1 = t1->next = cur1;
} else if (cur2) {
t1= t1->next = cur2;
}
head = h1;
return;
}
ListNode* reverse(ListNode* head) {
ListNode *pre = , *cur = head, *ne = ;
while (cur) {
ne = cur->next;
cur->next = pre;
pre = cur;
cur = ne;
}
return pre;
}
};
【147】Insertion Sort List
【148】Sort List
【160】Intersection of Two Linked Lists （2018年12月1日，第一次review， ko）
找到两个链表的公共部分的第一个结点。没有公共部分返回空结点。
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
题解：分别获取两个链表的长度，让长的那个链表走的和短的一样长的位置，然后两个一起走。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int l1 = getLen(headA), l2 = getLen(headB);
int diff = ;
ListNode *cur1 = headA, *cur2 = headB;
if (l1 > l2) {
diff = l1 - l2;
for (int i = ; i < diff; ++i) {
cur1 = cur1->next;
}
} else if (l1 < l2) {
diff = l2 - l1;
for (int i = ; i < diff; ++i) {
cur2 = cur2->next;
}
}
while (cur1 && cur2) {
if (cur1 == cur2) {
return cur1;
}
cur1 = cur1->next;
cur2 = cur2->next;
}
return nullptr;
}
int getLen(ListNode* head) {
ListNode* cur = head;
int cnt = ;
while (cur) {
cur = cur->next;
cnt++;
}
return cnt;
}
};
【203】Remove Linked List Elements
【206】Reverse Linked List （2019年2月24日）
反转一个链表。
题解：使用 recursive方法 和 iterative方法。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) { return head; }
ListNode* nextNode = head->next;
ListNode* newHead = reverseList(nextNode);
nextNode->next = head;
head->next = nullptr;
return newHead;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre=, *cur=head, *ne=;
while(cur){
ne = cur->next;
cur->next = pre;
pre = cur;
cur = ne;
}
return pre;
}
};
【234】Palindrome Linked List
【237】Delete Node in a Linked List
【328】Odd Even Linked List
【369】Plus One Linked List (2018 年11月26日)
给一个头结点是高位数字的链表整数加一。返回新链表。
题解：普通解法可以先搞成一个string 或者vector，再做高精度加。我是先翻转链表，然后加一，然后再翻转一次。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) {return head;}
h1 = head;
h1 = reverseListNode();
ListNode* cur = h1, *pre = ;
int carry = ;
while (carry == && cur || cur == h1) {
int num = cur == h1 ? cur->val + : carry + cur->val;
cur->val = num % ;
carry = num / ;
pre = cur;
cur = cur->next;
}
if (carry) {
pre->next = new ListNode(carry);
}
h1 = reverseListNode();
return h1;
}
ListNode* h1;
ListNode* reverseListNode() {
if (!h1) {return h1;}
ListNode* pre = , *cur = h1, *next = cur->next;
while (cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
【379】Design Phone Directory
【426】Convert Binary Search Tree to Sorted Doubly Linked List
【430】Flatten a Multilevel Doubly Linked List
【445】Add Two Numbers II (2018年11月26日)
给了两个链表，每个链表代表一个数，头结点代表最高位的数字，求两个链表的累加和，返回一个链表。（题目要求不能翻转链表）
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
题解：我是分别遍历两个链表，然后存在了两个string里面，string里面做高精度加法。然后把结果的string再搞成一个链表，返回。（也可以把string搞成vector，一样的）
/**
* 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) {
if (l1 == nullptr || l2 == nullptr) {
return l1 == nullptr ? l2 : l1;
}
string s1 = List2Str(l1), s2 = List2Str(l2);
string s3 = addString(s1, s2);
ListNode *head = , *tail = ;
for (int i = ; i < s3.size(); ++i) {
ListNode* node = new ListNode((s3[i] - ''));
if (!head) {
tail = head = node;
} else {
tail = tail->next = node;
}
}
return head;
}
string List2Str(ListNode* head) {
ListNode* h1 = head;
string ret = "";
while (h1) {
ret += to_string(h1->val);
h1 = h1->next;
}
return ret;
}
string addString(const string& s1, const string& s2) {
int carry = ;
string ret = "";
int size = min(s1.size(), s2.size());
int s1size = s1.size(), s2size = s2.size();
for (int k = ; k <= size; ++k) {
int num = (s1[s1size-k] - '') + (s2[s2size-k] - '') + carry;
string str = to_string(num % );
carry = num / ;
ret = str + ret;
}
if (size < s1size) {
const int leftsize = s1size - size;
for (int i = leftsize - ; i >= ; --i) {
int num = (s1[i] - '') + carry;
string str = to_string(num % );
carry = num / ;
ret = str + ret;
}
} else if (size < s2size) {
const int leftsize = s2size - size;
for (int i = leftsize - ; i >= ; --i) {
int num = (s2[i] - '') + carry;
string str = to_string(num % );
carry = num / ;
ret = str + ret;
}
}
if (carry) {
ret = to_string(carry) + ret;
}
return ret;
}
};
【707】Design Linked List
【708】Insert into a Cyclic Sorted List
【725】Split Linked List in Parts （2018年11月26日）
把一个链表分解成 k 个parts， 要求每个 parts 均匀分布，就是任意两个部分之间的长度不能相差大于一。
Return a List of ListNode's representing the linked list parts that are formed.
Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]
Example 1:
Input:
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].
Example 2:
Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
题解：先算总长度，然后把每个部分最短的长度算出来base，再把有几个部分需要加一算出来addition，然后开始分解就好啦。主要注意分解完了之后tail->next 要指向空指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* root, int k) {
vector<ListNode*> ret;
int n = getLen(root);
int base = n / k;
int addition = n % k;
ListNode* head = root;
for (int i = ; i < addition; ++i) { //base + 1
const int tot = base + ;
ListNode *h1 = , *t1 = ;
for (int j = ; j < tot; ++j) {
if (h1 == ) {
t1 = h1 = head;
} else {
t1 = t1->next = head;
}
head = head->next;
}
if(t1) {t1->next = ;}
ret.push_back(h1);
}
for (int i = ; i < k - addition; ++i) { //base
const int tot = base;
ListNode* h1 = , *t1 = ;
for (int j = ; j < tot; ++j) {
if (h1 == ) {
t1 = h1 = head;
} else {
t1 = t1->next = head;
}
head = head->next;
}
if (t1) {t1->next = ;}
ret.push_back(h1);
}
return ret;
}
int getLen(ListNode* root) {
ListNode* head = root;
if (!head) {return ;}
int ret = ;
while (head) {
ret++;
head = head->next;
}
return ret;
}
/*
void print(ListNode* h1) {
ListNode* head = h1;
while (head) {
printf("%d -> ", head->val);
head = head->next;
}
}
*/
};
【817】Linked List Components (2019年2月9日，谷歌tag复习)（M）
给了一个链表和一个集合G（G是链表元素的子集），如果在链表中两个相邻的元素算一个component，返回这个集合G中有多少个component。
题解：遍历链表，如果当前的结点在G中的话，如果没有component的头结点，就把当前结点当作一个component的头结点，如果有就继续遍历。如果当前结点不在G中的话，说明前面的component已经结束，把father清空。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
if (!head) {return ;}
set<int> st(G.begin(), G.end());
int cnt = ;
ListNode *cur = head, *father = nullptr;
while (cur) {
if (st.find(cur->val) == st.end()) {
father = nullptr;
} else {
if (!father) {
father = cur;
cnt++;
}
}
cur = cur->next;
}
return cnt;
}
};
【876】Middle of the Linked List