LinkedList
About 591 words
141 LinkedListCycle
该题是一个链表中是否有环的问题，可以使用哈希表或者快慢指针来解决。
#include <bits/stdc++.h>
using namespace std;
// Leetcode link: https://leetcode.com/problems/linked-list-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)
// Floyd's Tortoise and Hare algorithm
{
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr and fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
bool hasCycle_plain(ListNode* head)
{
unordered_set<ListNode*> dict;
while (head != nullptr) {
auto query = dict.find(head);
if (query != dict.end()) return true;
dict.insert(head);
head = head->next;
}
return false;
}
};2 Add
该题是一个链表的加法，需要注意进位的处理。
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() :
val(0), next(nullptr) { }
ListNode(int x) :
val(x), next(nullptr) { }
ListNode(int x, ListNode* next) :
val(x), next(next) { }
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* head = new ListNode;
ListNode* ptr = head;
int p = 0;
int v = 0;
while (l1 != nullptr || l2 != nullptr || p != 0) {
v = p;
if (l1 != nullptr)
v += l1->val;
if (l2 != nullptr)
v += l2->val;
p = v / 10;
v %= 10;
ptr->next = new ListNode();
ptr->next->val = v;
ptr = ptr->next;
if (l1 != nullptr)
l1 = l1->next;
if (l2 != nullptr)
l2 = l2->next;
}
ListNode* ans = head->next;
delete head;
return ans;
}
};876 Middle
该题引入一个核心想法，即快慢指针。
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode()
: val(0)
, next(nullptr)
{
}
ListNode(int x)
: val(x)
, next(nullptr)
{
}
ListNode(int x, ListNode* next)
: val(x)
, next(next)
{
}
};
class Solution {
public:
ListNode* middleNode(ListNode* head)
{
if (head->next == nullptr)
return head;
ListNode *fast = head->next, *slow = head;
while (fast) {
fast = fast->next;
slow = slow->next;
if (fast)
fast = fast->next;
}
return slow;
}
};82 RemoveDuplicates
该题难度中偏易，需要处理头部节点和尾部节点为空的特殊情况。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void printall(ListNode* head) {
while (head) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
ListNode* deleteDuplicates(ListNode* head) {
ListNode* prior = new ListNode(); // the node prior to begin
ListNode* real_head = prior; // real list head
ListNode* begin = head; // position from which the deletion starts
ListNode* end; // position at which the deletion stops, not inclduing this node
prior -> next = head; // a placehoder node at the beginning
while (begin) {
end = begin->next;
// if duplicates are detected
if(end && end->val == begin->val) {
// search for the ending
while (end && end -> val == begin-> val) {
end = end -> next;
}
// deletion
// cout << "begin: " << begin->val << " end: " << (end ? end->val : -1) <<endl;
ListNode* start = begin;
while (start != end) {
ListNode* ptr = start;
start = start -> next;
delete ptr;
}
// concat
prior -> next = end;
// if no duplicates
} else {
prior = prior -> next;
}
// always set begin to prior -> next to detect duplicates
begin = prior -> next;
// printall(real_head);
}
ListNode* ret = real_head->next;
delete real_head;
return ret;
}
};