Leetcode刷题
二. 链表 删除元素 常用操作 反转 环形
题目索引
https://www.acwing.com/activity/content/punch_the_clock/31/
1. LeetCode 203. 移除链表元素
https://leetcode-cn.com/problems/remove-linked-list-elements/
2. LeetCode 707. 设计链表
https://leetcode-cn.com/problems/design-linked-list/
3. LeetCode 206. 反转链表
https://leetcode-cn.com/problems/reverse-linked-list/
4. LeetCode 19. 删除链表的倒数第N个节点
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
5. LeetCode 141. 环形链表
https://leetcode-cn.com/problems/linked-list-cycle/
6. LeetCode 142. 环形链表 II
https://leetcode-cn.com/problems/linked-list-cycle-ii/
解题笔记
1. LeetCode 203. 移除链表元素
https://leetcode-cn.com/problems/remove-linked-list-elements/
虚拟头节点的使用会使问题简单很多
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
auto *dummy = new ListNode(-1);
dummy->next = head;
for (auto p = dummy; p; p = p->next) {
auto q = p->next;
while(q && q->val == val) {
auto temp = q;
q = q->next;
delete temp;
}
p->next = q;
}
return dummy->next;
}
};
2. LeetCode 707. 设计链表
https://leetcode-cn.com/problems/design-linked-list/
class MyLinkedList {
struct Node{
int val;
Node *next;
Node(int _val): val(_val),next(nullptr){}
}*head;
public:
MyLinkedList() {
head = nullptr;
}
int get(int index) {
if(index < 0) {
return -1;
}
auto p = head;
for (int i = 0; i < index && p; i++) {
p = p->next;
}
if(!p) {
return -1;
}
return p->val;
}
void addAtHead(int val) {
auto temp = new Node(val);
temp->next = head;
head = temp;
}
void addAtTail(int val) {
//添加尾节点要判空
if(!head) {
head = new Node(val);
}else {
auto temp = new Node(val);
auto p = head;
while(p->next) {
p = p->next;
}
p->next = temp;
}
}
void addAtIndex(int index, int val) {
if(index <= 0) {
addAtHead(val);
}else {
int len = 0;
auto p = head;
while(p) {
len++;
p = p->next;
}
if(index == len) {
addAtTail(val);
}else if(index < len){
p = head;
for (int i = 0; i < index-1; i++) {
p = p->next;
}
auto temp = new Node(val);
temp->next = p->next;
p->next = temp;
}
}
}
void deleteAtIndex(int index) {
auto p = head;
int len = 0;
while(p){
p = p->next;
len++;
}
if(index >= 0 && index < len) {
if(index == 0) {
auto temp = head;
head = head->next;
delete temp;
}else {
p = head;
for (int i = 0; i < index - 1; i++) {
p = p->next;
}
auto temp = p->next;
p->next = p->next->next;
delete temp;
}
}
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
3. LeetCode 206. 反转链表
https://leetcode-cn.com/problems/reverse-linked-list/
建立一个虚拟节点
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head) {
return nullptr;
}
ListNode *pre = nullptr, *p = head;
while(p){
auto temp = p->next;
p->next = pre;
pre = p;
p = temp;
}
return pre;
}
};
不建立虚拟节点
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head) {
return nullptr;
}
ListNode *pre = head, *p = head->next;
while(p){
auto temp = p->next;
p->next = pre;
pre = p;
p = temp;
}
head->next = nullptr;
return pre;
}
};
递归方法
把函数看做一个黑箱
reverseList(head):head为头结点的链表返回其逆序链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next) {
return head;
}
auto tail = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return tail;
}
};
4. LeetCode 19. 删除链表的倒数第N个节点
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
auto dummy = new ListNode(-1);
dummy->next = head;
int len = 0;
auto p = dummy;
while(p) {
len++;
p = p->next;
}
p = dummy;
for (int i = 0; i < len - n - 1; i++) {
//找到倒数第n+1个点
p = p->next;
}
p->next = p->next->next;
return dummy->next;
}
};
5. LeetCode 141. 环形链表
https://leetcode-cn.com/problems/linked-list-cycle/
如何判断一个链表有环
哈希表判断地址值
经典思路：快慢指针
快指针每次往后跳两格，慢指针每次往后跳一格
有环：会相遇
无环：快指针会先到空域
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head || !head->next) {
return false;
}
auto f = head->next, s = head;
while(f) {
s = s->next;
f = f->next;
if(f == nullptr) {
return false;
}
f = f->next;
if(s == f) {
return true;
}
}
return false;
}
};
6. LeetCode 142. 环形链表 II
https://leetcode-cn.com/problems/linked-list-cycle-ii/
不仅判断有没有环，还判断有环时入口在哪
一个指针从相遇点走，一个从起点走，相遇点就是环的入口
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head || !head->next) {
return nullptr;
}
auto f = head, s = head;
while(f) {
s = s->next;
f = f->next;
if(!f) {
return nullptr;
}
f = f->next;
if (s == f) {
s = head;
// f = f->next;
while(s != f) {
s = s->next;
f = f->next;
}
return s;
}
}
return nullptr;
}
};
