LeetCode hot100---链表专题(C++语言)
1、相交链表
(1)题目描述以及输入输出
(1)题目描述:
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交点,返回 null 。
(2)输入输出描述:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
关键思路:
定义两个节点同时从两个链表遍历,遍历到头后,从另一个链表开始遍历,到相遇处就是交点
(2)代码块
/**
* 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) {
ListNode *A = headA;
ListNode *B = headB;
while(A != B)
{
A = (A == NULL)?headB:A->next;
B = (B == NULL)?headA:B->next;
}
return A;
}
};
2、翻转链表
(1)题目描述以及输入输出
(1)题目描述:
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
(2)输入输出描述:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
关键思路:
从链表头开始遍历,cur保留当前节点,每次遍历更新pre cur_next位置
(2)代码块
/**
* 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)
{
ListNode* cur = head;
ListNode* pre = nullptr;
ListNode* cur_next = nullptr;
while(cur != nullptr)
{
cur_next = cur->next;
cur->next = pre;
pre = cur;
cur = cur_next;
}
return pre;
}
};
3、回文链表
(1)题目描述以及输入输出
(1)题目描述:
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
(2)输入输出描述:
输入:head = [1,2,2,1]
输出:true
关键思路:
先遍历链表,用数组承接链表元素,接着使用双指针判断数组首尾元素是否一直相等。
(2)代码块
/**
* 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:
bool isPalindrome(ListNode* head)
{
vector<int> record;
ListNode* phead = head;
int left,right;
if(head == nullptr)return false;
while(phead)
{
record.push_back(phead->val);
phead = phead->next;
}
left = 0;
right = record.size()-1;
while(left<=right)
{
if(record[left] != record[right])
return false;
left++;
right--;
}
return true;
}
};
4、环形链表
(1)题目描述以及输入输出
(1)题目描述:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
(2)输入输出描述:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
关键思路:
使用快慢双指针遍历链表,快指针每次走两步,慢指针走1步。
若存在环,总会相遇。
(2)代码块
/**
* 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) {
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)return true;
}
return false;
}
};
5、环形链表||
(1)题目描述以及输入输出
(1)题目描述:
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。不允许修改 链表。
(2)输入输出描述:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
关键思路:
使用快慢双指针遍历链表,快指针每次走两步,慢指针走1步。若存在环,总会相遇。
相遇后要找到环的入口节点。x+n*(y+z) = 2*(x+y),假如在y点相遇。相遇后快指针移到开头,快慢指针同时向后遍历,相遇处即交点。
(2)代码块
/**
* 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)
{
ListNode* fast = head;
ListNode* slow = head;
while(1)
{
if(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
break;
}
else
return NULL;
}
fast = head;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
};
6、合并两个有序链表
(1)题目描述以及输入输出
(1)题目描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
(2)输入输出描述:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
关键思路:
定义数组保存两个链表中各项的值,对于每个值开辟节点保存到链表中
(2)代码块
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2)
{
ListNode* p = list1;
if(list1 == NULL && list2 == NULL)return NULL;
vector<int> record;
while(p)
{
record.push_back(p->val);
p = p->next;
}
p = list2;
while(p)
{
record.push_back(p->val);
p = p->next;
}
sort(record.begin(),record.end());
ListNode* head = new ListNode(record[0]);
p = head;
for(int i = 1;i<record.size();i++)
{
ListNode* tmp = new ListNode(record[i]);
p->next = tmp;
p = p->next;
}
return head;
}
};
7、两数相加
(1)题目描述以及输入输出
(1)题目描述:
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
(2)输入输出描述:
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
关键思路:
遍历两个链表,将其值相加得到record,创建新节点保存各项值的个位,然后record保存值的十位,然后平移cur节点,进入下一轮循环。
(2)代码块
/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
int record = 0;
while(l1||l2||record)
{
if(l1)
{
record += l1->val;
l1 = l1->next;
}
if(l2)
{
record += l2->val;
l2 = l2->next;
}
cur->next = new ListNode(record%10);
cur = cur->next;
record /= 10;
}
return dummy->next;
}
};
8、删除链表倒数第N个节点
(1)题目描述以及输入输出
(1)题目描述:
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
(2)输入输出描述:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
关键思路:
定义快慢指针,快指针先走N步,接着快慢指针同时向后遍历,快指针遍历到末尾时,慢指针指向的是待删除元素的前一节点。跳过节点即可,
(2)代码块
/**
* 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)
{
ListNode* dummyhead = new ListNode();
dummyhead->next = head;
ListNode* fast = dummyhead;
ListNode* slow = dummyhead;
while(n--)
{
fast = fast->next;
}
while(fast->next != nullptr)
{
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummyhead->next;
}
};
9、两两交换链表中的节点
(1)题目描述以及输入输出
(1)题目描述:
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。
(2)输入输出描述:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
关键思路:
交换两个节点要保留四个节点,chang1、change2、pre、nect_change;做完赋值后,开始构建链表。
(2)代码块
/**
* 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* swapPairs(ListNode* head)
{
ListNode* pre = new ListNode(); // 两节点的前一节点
pre->next = head;
ListNode* dummyhead = pre;
ListNode* next_change1 = nullptr;// 两节点的后一节点
ListNode* change1 = nullptr;
ListNode* change2 = nullptr;
while((pre->next != nullptr) && (pre->next->next != nullptr))
{
change1 = pre->next;
change2 = pre->next->next;
next_change1 = pre->next->next->next;
pre->next = change2; // 使得链表结构完整pre->2->1->3->4
change2->next = change1;
change1->next = next_change1; // 交换节点
pre = change1; // 更新下两节点的前节点
}
return dummyhead->next;
}
};
10、随机链表的复制
(1)题目描述以及输入输出
(1)题目描述:
深拷贝随机链表
关键思路:
使用map<Node*,Node*>进行链表拷贝,先遍历链表,一个cur对应一个拷贝出来的新节点。此时只是在哈希表中保存了所有节点。
接着再次遍历链表,进行哈希表节点的链接。
(2)代码块
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head)
{
unordered_map<Node*,Node*> record;
Node* cur = head;
for(cur = head;cur;cur = cur->next)
{
record[cur] = new Node(cur->val);//先把当前节点拷贝下来
}
for(cur = head;cur;cur = cur->next)
{
if(cur->next)record[cur]->next = record[cur->next];
if(cur->random)record[cur]->random = record[cur->random];
}
return record[head];
}
};
11、排序链表
(1)题目描述以及输入输出
(1)题目描述:
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表
(2)输入输出描述
输入:head = [4,2,1,3]
输出:[1,2,3,4]
关键思路:
遍历链表,将链表各节点值保存至数组中,对数组排序,接着再遍历链表,修改链表中各节点值
(2)代码块
/**
* 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* sortList(ListNode* head)
{
vector<int> record;
ListNode *phead = head;
while(phead)
{
record.push_back(phead->val);
phead = phead->next;
}
sort(record.begin(),record.end());
phead = head;
int k = 0;
while(phead)
{
phead->val = record[k++];
phead = phead->next;
}
return head;
}
};
原文地址:https://blog.csdn.net/qq_54017644/article/details/142702641
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!