148. Sort List链表排序
-
归并（top down）
使用快慢指针将链表分成两个部分；
l1, l2 = split(l)
l1',l2' = sortList(l1), sortList(l2) (递归，当l1和l2只有一个节点时，sortList返回本身)，时间复杂度logN，空间复杂度logN
merge(l1', l2')，时间复杂度N
-
下面的代码需要注意，swap(l1, l2)，交换的指针指向的内容， 包括val和next!
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head==nullptr|| head->next==nullptr)
return head;
ListNode* slow = head, *fast = head->next;
while(fast!=nullptr && fast->next!=nullptr){
fast = fast->next->next;
slow = slow->next;
}
ListNode* mid = slow->next;
slow->next = nullptr;
return mergeList(sortList(head), sortList(mid));
}
private:
ListNode* mergeList(ListNode* l1, ListNode* l2){
ListNode dummy(0); //定义在栈上，不用关心内存的问题
ListNode* tail = &dummy;
while(l1 && l2){
if(l1->val > l2->val){
swap(l1, l2);
}
tail->next = l1;
l1 = l1->next;
tail = tail->next;
}
if(l1) tail->next = l1;
if(l2) tail->next = l2;
return dummy.next;
}
};
- 归并(bottom up) -- O(1)的空间复杂度
- 归并(bottom up) -- O(1)的空间复杂度
- 两两merge，需要有一个split函数，将链表进行分割，按照1,2,4,8,16...的间隔进行分割；
- merge的时候不止传回merge后链表的头结点，还需要传回尾节点，以此来实现滚动；
class Solution {
public:
ListNode* sortList(ListNode* head) {
// 0 or 1 element, we are done.
if (!head || !head->next) return head;
int len = 1;
ListNode* cur = head;
while (cur = cur->next) ++len;
ListNode dummy(0);
dummy.next = head;
ListNode* l;
ListNode* r;
ListNode* tail;
for (int n = 1; n < len; n <<= 1) {
cur = dummy.next; // partial sorted head
tail = &dummy;
while (cur) {
l = cur;
r = split(l, n);
cur = split(r, n);
auto merged = merge(l, r);
tail->next = merged.first;
tail = merged.second;
}
}
return dummy.next;
}
private:
// Splits the list into two parts, first n element and the rest.
// Returns the head of the rest.
ListNode* split(ListNode* head, int n) {
while (--n && head)
head = head->next;
ListNode* rest = head ? head->next : nullptr;
if (head) head->next = nullptr;
return rest;
}
// Merges two lists, returns the head and tail of the merged list.
pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val > l2->val) swap(l1, l2);
tail->next = l1;
l1 = l1->next;
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
while (tail->next) tail = tail->next;
return {dummy.next, tail};
}
};
- 链表快排
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head == NULL) return head;
Quick_Sort(head, NULL);
return head;
}
void Quick_Sort(ListNode* head, ListNode* end)
{
if (head != end && head->next != end)
{
ListNode* ptr = head;
while(ptr->next != end) ptr = ptr->next; // 取链表最后一个元素作为主元
int pivot = ptr->val;
ListNode* p1 = head;
ListNode* p2 = head;
while(p2->next != end)
{
if(p2->val < pivot)
{
int temp = p2->val;
p2->val = p1->val;
p1->val = temp;
p1 = p1->next;
}
p2 = p2->next;
}
p2->val = p1->val;
p1->val = pivot;
Quick_Sort(head, p1); // 此时 p1 指向 pivot，前一半链表头为 head，尾为 p1
Quick_Sort(p1->next, end); // 后一半链表头为 p1->next，尾为 end
}
}
};
25.Reverse Nodes in k-Group
- 在每k个链表内进行逆序
-
k个链表内的数逆序方式为，如下图：
将第一个数设为tail（因为逆序后肯定会排到最后面）
设置curr节点，从tail->next一直到last前一个节点，
将每个curr移动到prev->next,作为第一个节点
每次移动curr前，设置next节点，也就是curr->next，实现curr滚动
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(head == NULL) return NULL;
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
while(prev != NULL){
prev = reverse(prev,k);
}
return dummy.next;
}
private:
ListNode* reverse(ListNode* prev, int k){
ListNode* last = prev;
for(int i=0; i<k+1; ++i){
last = last->next;
if(last == NULL && i!=k)
return NULL;
} //设置要进行逆序的区间，到last就截止
ListNode* tail = prev->next;
ListNode* curr = tail->next;
while(curr != last){
ListNode* next = curr->next;
curr->next = prev->next;
prev->next = curr;
tail->next = next;
curr = next;
}
return tail;
}
};
使用stack的方式
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(head == NULL) return NULL;
ListNode dummy(0);
dummy.next = head;
stack<ListNode *> sliding;
ListNode* curr = &dummy;
ListNode* next = curr->next;
while(next != NULL){
for(int i=0; i<k && next!=NULL; ++i){
sliding.push(next);
next = next->next;
}
if(sliding.size() != k) return dummy.next;
while(sliding.size() != 0){
curr->next = sliding.top();
sliding.pop();
curr = curr->next;
}
curr->next = next;
}
return dummy.next;
}
};
141. Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/
这道题是二刷的题目。我把之前的代码删掉，重新做了一遍，发现这次想出来的方法更简单。解法二和解法三是之前在雁栖湖做的。
解法一：将已经遍历过的节点的value都置为INT_MAX，接着往后遍历，如果后面出现节点值为INT_MAX，那么说明链表中存在Cycle
/**
* 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) {
ListNode* p;
p = head;
while(p != NULL){
p->val = INT_MAX;
p = p -> next;
if(p != NULL && p->val == INT_MAX)
return true;
}
return false;
}
};
解法二：使用哈希set的方法，将遍历过的节点插入到哈希表中
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> visited;
while(head){
if(visited.count(head))
return true;
visited.insert(head);
head = head->next;
}
return false;
}
};
解法三：使用快慢指针，快指针一次走两步，慢指针一次走一步，有环的话快指针会在环里追到慢指针。
class Solution {
public:
bool hasCycle(ListNode *head) {
auto fast=head;
auto slow=head;
while(fast){
if(!fast->next)
return false;
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return true;
}
return false;
}
};
*146. LRU Cache
https://leetcode.com/problems/lru-cache/
这是一道很难的设计题，需要使用多种容器进行操作。我对C++容器的使用还是比较陌生，所以解起来难度比较大，希望自己下次再看到这道题的时候，整理一下C++容器的用法，加深理解。
[http://zxi.mytechroad.com/blog/hashtable/leetcode-146-lru-cache/]
class LRUCache {
public:
LRUCache(int capacity) {
capacity_ = capacity;
}
int get(int key) {
const auto it = m_.find(key);
// If key does not exist
if (it == m_.cend()) return -1;
// Move this key to the front of the cache
cache_.splice(cache_.begin(), cache_, it->second);
return it->second->second;
}
void put(int key, int value) {
const auto it = m_.find(key);
// Key already exists
if (it != m_.cend()) {
// Update the value
it->second->second = value;
// Move this entry to the front of the cache
cache_.splice(cache_.begin(), cache_, it->second);
return;
}
// Reached the capacity, remove the oldest entry
if (cache_.size() == capacity_) {
const auto& node = cache_.back();
m_.erase(node.first);
cache_.pop_back();
}
// Insert the entry to the front of the cache and update mapping.
cache_.emplace_front(key, value);
m_[key] = cache_.begin();
}
private:
int capacity_;
list<pair<int,int>> cache_;
unordered_map<int, list<pair<int,int>>::iterator> m_;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
725. Split Linked List in Parts
https://leetcode.com/problems/split-linked-list-in-parts/
这一题比较无聊，主要是考察list的操作
/**
* 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*> ans(k, nullptr);
int inputLength = 0;
for(ListNode* head = root; head; head = head->next){
++inputLength;
}
int numOfEachElement = inputLength / k;
int numOfAdd = inputLength % k;
vector<int> sizeOfEachElement;
for(int i=0; i<k; ++i){
if(numOfAdd-- > 0){
sizeOfEachElement.push_back(numOfEachElement+1);
}
else{
sizeOfEachElement.push_back(numOfEachElement);
}
}
ListNode* p = nullptr;
ListNode* head = root;
for(int j=0; j<k; ++j){
if(sizeOfEachElement[j] == 0){
continue;
}
ans[j] = head;
while(--sizeOfEachElement[j] >= 0){
p = head;
head = head->next;
}
p->next = nullptr;
}
return ans;
}
};
817. Linked List Components
https://leetcode.com/problems/linked-list-components/
题目大意：给你一个链表，再给你一些合法的节点，问你链表中有多少个连通分量（所有节点必须合法）。
解法一：把vector G 初始化为unordered_set，方便查找。然后遍历所有节点，倘若当前节点在G中，并且邻节点为空或值不在G中，那么为不连通
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
unordered_set<int> g(G.begin(), G.end());
int ans = 0;
while(head){
if(g.count(head->val) && (!head->next || !g.count(head->next->val)))
ans++;
head = head->next;
}
return ans;
}
};
解法二：Graph Traversal using DFS（By huahua）
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
unordered_set<int> f(G.begin(), G.end());
unordered_map<int, vector<int>> g;
int u = head->val;
while (head->next) {
head = head->next;
int v = head->val;
if (f.count(v) && f.count(u)) {
g[u].push_back(v);
g[v].push_back(u);
}
u = v;
}
int ans = 0;
unordered_set<int> visited;
for (int u : G) {
if (visited.count(u)) continue;
++ans;
dfs(u, g, visited);
}
return ans;
}
private:
void dfs(int cur, unordered_map<int, vector<int>>& g, unordered_set<int>& visited) {
if (visited.count(cur)) return;
visited.insert(cur);
for (const int next : g[cur])
dfs(next, g, visited);
}
};
21. Merge Two Sorted Lists
dummy作用：在栈上申请一个ListNode对象，dummy.next 指向head
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail=&dummy;
while(l1 && l2){
if(l1->val < l2->val){
tail->next = l1;
l1 = l1->next;
}
else{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if(l1) tail->next = l1;
if(l2) tail->next = l2;
return dummy.next;
}
};
