Linked List
83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode dummy(0);
dummy.next = head;
ListNode* pre = &dummy;
ListNode* cur = head;
while (cur) {
while (cur && cur->next && cur->val == cur->next->val) cur = cur->next;
pre->next = cur;
pre = cur;
if (cur) cur = cur->next;
}
if (pre) pre->next = nullptr;
return dummy.next;
}
};
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.
Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (!head || m == n) return head;
ListNode* pre = nullptr;
ListNode* cur = head;
int start = m;
while (--start && cur) {
pre = cur;
cur = cur->next;
}
if (start != 0 || !cur) return head;
ListNode* head1 = cur;
ListNode* pre1 = cur;
ListNode* cur1 = cur->next;
int cnt = n - m;
while (cur1 && cnt--) {
ListNode* tmp = cur1->next;
cur1->next = pre1;
pre1 = cur1;
head1 = cur1;
cur1 = tmp;
}
if (pre) pre->next = head1;
cur->next = cur1;
if (m == 1) return head1;
return head;
}
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* cur = head;
ListNode* next = head->next;
cur->next = nullptr;
ListNode* newHead = reverseList(next);
next->next = cur;
return newHead;
}
};
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.
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
ListNode* next = head->next;
while (cur) {
while (cur && cur->next && cur->val == cur->next->val) {
int val = cur->val;
while (cur && cur->val == val) cur = cur->next;
}
//if (pre)
pre->next = cur;
pre = cur;
if (cur) cur = cur->next;
}
head = dummy->next;
delete dummy;
return head;
}
};
138. Copy List with Random Pointer
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (!head) return nullptr;
RandomListNode* cur = head;
RandomListNode* pre = nullptr;
while (cur) {
RandomListNode* copy = new RandomListNode(cur->label);
copy->next = cur->next;
cur->next= copy;
cur = copy->next;
}
pre = head;
cur = head->next;
while (cur) {
if (pre->random)
cur->random = pre->random->next;
else
cur->random = nullptr;
pre = cur->next;
if (!pre) break;
cur = pre->next;
}
RandomListNode* newHead = head->next;
pre = head;
cur = head->next;
while (cur) {
pre->next = cur->next;
pre = cur->next;
if (!pre) break;
cur->next = pre->next;
cur = pre->next;
}
return newHead;
}
};
142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up: Can you solve it without using extra space?
/**
* 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 || !head->next) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
bool hasCycle = false;
while (fast) {
if (!fast->next) return nullptr;
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
hasCycle = true;
break;
}
}
if (!hasCycle) return nullptr;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
146. LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
class LRUCache{
public:
LRUCache(int capacity) : capacity(capacity) {
}
int get(int key) {
int ret = -1;
if (cache.find(key) != cache.end()) {
ret = cache[key]->second;
visit_queue.splice(visit_queue.begin(), visit_queue, cache[key]);
}
return ret;
}
void set(int key, int value) {
if (cache.find(key) != cache.end()) {
cache[key]->second = value;
visit_queue.splice(visit_queue.begin(), visit_queue, cache[key]);
} else {
if (cache.size() == capacity) {
cache.erase(visit_queue.back().first);
visit_queue.pop_back();
}
visit_queue.push_front({key, value});
cache[key] = visit_queue.begin();
}
}
private:
unordered_map<int, list<pair<int, int>>::iterator> cache;
list<pair<int, int>> visit_queue;
int capacity;
};
147. Insertion Sort List
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode dummy(0);
// dummy.next = head;
ListNode* cur = head;
ListNode* next = nullptr;
while (cur) {
next = cur->next;
cur->next = nullptr;
// insert cur to the list;
ListNode* pre = &dummy;
ListNode* tmp = dummy.next;
while (tmp && tmp->val < cur->val) {
pre = tmp;
tmp = tmp->next;
}
pre->next = cur;
cur->next = tmp;
// move to next value;
cur = next;
}
head = dummy.next;
return head;
}
};
206. Reverse Linked List
/**
* 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* pre = head;
// ListNode* cur = head->next;
// pre->next = nullptr;
// ListNode* newHead = nullptr;
// while (cur) {
// ListNode* next = cur->next;
// cur->next = pre;
// pre = cur;
// newHead = cur;
// cur = next;
// }
// return newHead;
ListNode* cur = head;
ListNode* next = head->next;
cur->next = nullptr;
ListNode* newHead = reverseList(next);
next->next = cur;
return newHead;
}
};