链表相关题目题解
返回链表倒数第k个元素
- 快慢指针，第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可
class Solution: |
栈。把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可
链表反序
- 直接遍历
- 递归
链表公共节点
给定两个单链表
A，B，假设一定含有公共结点，返回第一个公共结点的指针。双指针
class Solution { |
- 上述代码是从第一个链表的尾部循环到第二个链表的头部，第二个链表从尾部循环到第一个链表的头部，相当于是把一个链表完整的连接在了另一个后面构成一个长度为m+n的新的链表，长度相等，而且保留原来的相同的节点
找带环链表的入口位置
返回带有环的链表的环的入口节点
理解：假设从开始到相遇位置的总距离是x+y，x是直线距离，y是在环上的距离，那么此时快指针走过的路径长度是2（x+y），也就意味着环上剩余的长度为x+y,此时将其中一个指针移动到头部，另一个保持在原地，二者都按照1的步长运动，走到入口节点的距离是相同的都是x+y，所以必定会在环的入口相遇
class Solution { |
leetcode 146. LRU缓存
- 实现一个在容量上限达到之后弹出上次使用时间到现在最长的缓存项目的数据结构
struct cacheLine
{
int value;
int key;
cacheLine* next;
cacheLine* prev;
cacheLine(int b, int a):value(a), key(b), next(NULL), prev(NULL){}
};
class LRUCache {
public:
int capa;
int usedCnt;
cacheLine* head;
cacheLine* tail;
unordered_map<int, cacheLine*> m;
LRUCache(int capacity) {
capa = capacity;
usedCnt = 0;
head = new cacheLine(-999, 0);
}
int get(int key)
{
if(m.count(key))
{
if(usedCnt>1&&m[key]->prev != head)
{
cacheLine* temp = head->next;
cacheLine* thisNode = m[key];
if(thisNode == tail)
{
tail = tail->prev;
}
if(thisNode->next)
{
thisNode->next->prev = thisNode->prev;
}
thisNode->prev->next = thisNode->next;
head->next = thisNode;
thisNode->next = temp;
thisNode->prev = head;
temp->prev = thisNode;
if(temp)
thisNode->next->prev =thisNode;
return thisNode->value;
}
else return m[key]->value;
}
else return -1;
}
void put(int key, int value)
{
if(m.count(key))
{
m[key]->value = value;
get(key);
return;
}
if(usedCnt>0 && usedCnt<capa)
{
cacheLine* temp = head->next;
cacheLine* newNode = new cacheLine(key, value);
temp->prev = newNode;
head->next = newNode;
newNode->prev = head;
newNode->next = temp;
m[key] = head->next;
++usedCnt;
}
else if(usedCnt == 0)
{
head->next = new cacheLine(key, value);
m[key] = head->next;
head->next->prev = head;
tail = head->next;
++usedCnt;
}
else if(usedCnt>1 && usedCnt == capa)
{
m.erase(m.find(tail->key));
tail->key = key;
tail->value = value;
m[key] = tail;
get(key);
}
else
{
m.erase(m.find(tail->key));
tail->key = key;
tail->value = value;
m[key] = tail;
}
}
};
/**
* 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);
*/链表选择排序
- 注意处理链表尾部和头部的问题
- 建立一个假头部
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode* dumHead = new ListNode(INT_MIN);
dumHead->next = head;
ListNode* newHead = dumHead, *cur = head;
int minVal = INT_MAX;
ListNode* prevOfMin;
while(newHead->next!=NULL)
{
cur = newHead;
while(cur->next!=NULL)
{
if(cur->next->val<minVal)
{
prevOfMin = cur;
minVal = cur->next->val;
}
cur = cur->next;
}
minVal = INT_MAX;
if(prevOfMin == newHead)
{
newHead = newHead->next;
continue;
}
ListNode* temp = newHead->next, *temp2 = prevOfMin->next->next;
newHead->next = prevOfMin->next;
prevOfMin->next->next = temp;
prevOfMin->next = temp2;
if(newHead->next)
newHead = newHead->next;
}
return dumHead->next;
}
};
链表插入排序
- 注意首先选择一个元素作为要插入的元素（保存这个元素的上一个元素这样方便修改，否则无法修改）
- 注意没找到插入点的处理方法
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode* dumHead = new ListNode(INT_MIN);
dumHead->next = head;
ListNode* cur, *pick = dumHead->next;
int temp;
while(pick->next)
{
cur = dumHead;
while((cur->next)&&(cur->next!=pick->next)&&(cur->next->val<=pick->next->val))
{
cur = cur->next;
}
if(cur->next == pick->next)
{
pick = pick->next;
continue;
}
ListNode* temp = cur->next;
ListNode*temp2 = pick->next->next;
cur->next = pick->next;
pick->next = temp2;
cur->next->next = temp;
}
return dumHead->next;
}
};Leetcode 206.反转链表
- 这题使用双指针方式不需要额外内存
- 注意记得消除第一个节点（也就是反转后最后一个节点）的next为NULL，防止内存错误
/**
* 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:
ListNode* reverseList(ListNode* head) {
if(!head || !(head->next))return head;
if(head->next->next == NULL)
{
ListNode* tmp = head->next;
head->next = NULL;
tmp->next = head;
return tmp;
}
ListNode* next, *cur, *tmp;
cur = head;
tmp = head->next;
next = head->next->next;
cur->next = NULL;
while(next)
{
tmp->next = cur;
cur = tmp;
tmp = next;
next = next->next;
}
tmp->next = cur;
return tmp;
}
};
151. 反转字符串中的单词
- 此题是先将整个字符串去掉多余的空格，然后将整个字符串反转（reverse），然后再将字符串中的每个单词字母反转
class Solution {
public:
string reverseWords(string s) {
int from = 0, to = 0;
while(s[from] == ' ')++from;
while(from<s.size())
{
if(s[from] == ' ')
{
s[to++] = s[from++];
while(from<s.size() && s[from] == ' ')
{
++from;
}
}
if(from<s.size())
s[to++] = s[from++];
}
s.resize(to);
while(s.back() == ' ')s.erase(s.end()-1);
reverse(s.begin(), s.end());
int start = 0;
while(start<s.size())
{
int beg = start, end;
while(start<s.size() && s[start]!=' ')
{
start++;
}
end = start-1;
while(beg<end)
{
char tmp = s[end];
s[end] = s[beg];
s[beg] = tmp;
end--;
beg++;
}
start++;
}
return s;
}
};
Leetcode 202. 快乐数
- 用快慢指针的方法，一个指针一次走两步，一个一次走一步
class Solution {
public:
int bitSquareSum(int n) {
int sum = 0;
while(n > 0)
{
int bit = n % 10;
sum += bit * bit;
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n, fast = n;
do{
slow = bitSquareSum(slow);
fast = bitSquareSum(fast);
fast = bitSquareSum(fast);
}while(slow != fast);
return slow == 1;
}
};