第一课:链表
1. 链表的必备知识要点(包括基础知识、刷题中使用的STL等知识)
2. 链表逆序(LeetCode 92,206. Reverse Linked List 1,2)
3. 求两个链表的交点(LeetCode 160. Intersection of Two Linked Lists)
4. 链表的节点交换(LeetCode 24. Swap Nodes in Pairs)
5. 链表求环(LeetCode 141,142. Linked List Cycle 1,2)
6. 链表重新构造(LeetCode 86. Partition List)
7. 复杂的链表复制(LeetCode 138. Copy List with Random Pointer)
8. 排序链表合并(2个与多个) (LeetCode 21,23 Merge Two(k) Sorted ListsLeetCode)
9. 剑指offer中 https://leetcode-cn.com/problem-list/xb9nqhhg/
10. 142. 环形链表 II https://leetcode-cn.com/problems/linked-list-cycle-ii/
链表模板
// 定义
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
链表逆序 LeetCode 92,206
#include <iostream>
using namespace std;
struct ListNode{
int val;
ListNode * next;
ListNode(int x): val(x),next(NULL) {}
};
class Solution{
public:
ListNode * reverselist(ListNode * head) { // 206
ListNode * pre = NULL;
ListNode * next = NULL;
while(head)
{
next = head ->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
ListNode * reverseList_m_n(ListNode * head,int m,int n){ // 92
ListNode * dummy = new ListNode(-1);
dummy->next = head;
ListNode *a = dummy;
for(int i = 0; i < m-1; i++) {
a = a->next;
}
ListNode *b = a->next;
ListNode *c = b->next;
for(int i = m; i < n; i++) {
ListNode * t = c->next;
c->next = b;
b = c;
c = t;
}
a->next->next = c;
a->next = b;
return dummy->next;
}
};
int main()
{
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(4);
ListNode e(5);
ListNode f(6);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = NULL;
cout << "start.." << endl;
ListNode* head = &a;
while(head) {
cout << head->val <<' ';
head = head->next;
}
cout << endl;
cout << "before.." << endl;
Solution res;
head = res.reverseList_m_n(&a,2,5);
while(head) {
cout << head->val <<' ';
head = head->next;
}
cout << endl;
return 0;
}
求两个链表的交
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto q = headA;
auto p = headB;
while(q != p) {
p? p = p->next:p = headB;
q? q = q->next:q = headA;
}
return q;
}
};
使用set
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
set<ListNode *> t;
while(headA) {
t.insert(headA);
headA = headA->next;
}
while(headB) {
if(t.find(headB) != t.end()) {
return headB;
}
headB = headB->next;
}
return NULL;
}
};
链表的节点交换(LeetCode 24. Swap Nodes in Pairs)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
for(auto p = dummy; p->next && p->next->next;) {
auto a = p->next,b = a->next;
p->next = b;
a->next = b->next;
b->next = a;
p = a;
}
return dummy->next;
}
};
链表求环(LeetCode 141,142. Linked List Cycle 1,2)
// 141 142
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head || !head->next) return false;
auto s = head,f = head->next;
while(f) {
s = s->next;
f = f->next;
if(!f) return false;
f = f->next;
if(s == f) return true;
}
return false;
}
};
// 141 使用set
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head || !head->next) return false;
set<ListNode*> s;
while(head) {
if(s.find(head) != s.end()) {
return head;
}
s.insert(head);
head = head ->next;
}
return false;
}
};
链表重新构造(LeetCode 86. Partition List)
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
auto lh = new ListNode(-1),rh = new ListNode(-1);
auto lt = lh,rt = rh;
for(auto p = head; p; p = p->next) {
if(p->val < x) {
lt->next = p;
lt = p;
} else {
rt ->next = p;
rt = p;
}
}
lt->next = rh->next;
rt->next = nullptr;
return lh->next;
}
};
复杂的链表复制(LeetCode 138. Copy List with Random Pointer)
class Solution {
public:
Node* copyRandomList(Node* head) {
// 复制一个小弟
for(auto p = head; p ; p = p->next->next) {
auto q = new Node(p->val);
q->next = p->next;
p->next = q;
}
// 复制random指针
for(auto p = head; p; p = p->next->next) {
if(p->random) {
p->next->random = p->random->next;
}
}
//拆分两个链表
auto dummy = new Node(-1),cur = dummy;
for(auto p = head;p ; p= p->next) {
auto q = p->next;
cur = cur->next = q;
p->next = q->next;
}
return dummy->next;
}
};
排序链表合并(2个与多个) (LeetCode 21,23 Merge Two(k) Sorted ListsLeetCode)
//21
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1),tail = dummy;
while(l1 && l2) {
if(l1->val < l2->val) {
tail = tail->next = l1;
l1 = l1->next;
} else {
tail = tail->next = l2;
l2 = l2->next;
}
}
if(l1) tail->next = l1;
if(l2) tail->next = l2;
return dummy->next;
}
};
// k路归并
class Solution {
public:
struct Cmp {
bool operator() (ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
auto dummy = new ListNode(-1), tail = dummy;
for (auto l : lists) if (l) heap.push(l);
while (heap.size()) {
auto t = heap.top();
heap.pop();
tail = tail->next = t;
if (t->next) heap.push(t->next);
}
return dummy->next;
}
};
剑指 Offer 06. 从尾到头打印链表
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> res;
while(head) {
res.push_back(head->val);
head = head->next;
}
reverse(res.begin(),res.end());
return res;
}
};
剑指 Offer 25. 合并两个排序的链表
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* tail = dummy;
while(l1 && l2) {
if(l1->val < l2->val) {
tail->next = l1;
tail = l1;
l1 = l1->next;
} else {
tail->next = l2;
tail = l2;
l2 = l2->next;
}
}
if(l1) tail->next = l1;
if(l2) tail->next = l2;
return dummy->next;
}
};
剑指 Offer 22. 链表中倒数第k个节点
// 快慢指针 yyds
//快慢指针,先让快指针走k步,然后两个指针同步走,当快指针走到头时,慢指针就是链表倒数第k个节点。
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
auto f = head,s = head;
while(f && k > 0) {
f = f->next;
k--;
}
while(f) {
f = f->next;
s = s->next;
}
return s;
}
};
// vector 方法
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
vector<ListNode*> res;
while(head != NULL) {
res.push_back(head);
head= head->next;
}
return res[res.size() - k];
}
};
- 环形链表 II
https://www.acwing.com/activity/content/code/content/1442399/
/**
* 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 NULL;
auto slow = head,fast = head;
while(slow && fast) {
// slow 走一步,fast走两步
slow = slow->next;
fast = fast->next;
if(fast == NULL) return NULL;
else fast = fast->next;
// 相遇了
if(slow == fast) {
slow = head; // 满指针回到头部,每次slow和fast都走一步
while(slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}
};
Linked List 实战题目
24. 两两交换链表中的节点
25. K 个一组翻转链表
课后作业
1
2
3
4
5
6
7