【基础算法】链表
1.两数相加
/**
* 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* newhead = new ListNode(-1);
ListNode* cur1 = l1, *cur2 = l2;
ListNode* prev = newhead;
int t = 0;
while(cur1 || cur2 || t)
{
if(cur1) {
t += cur1->val;
cur1 = cur1->next;
}
if(cur2) {
t += cur2->val;
cur2 = cur2->next;
}
prev->next = new ListNode(t % 10);
prev = prev->next;
t /= 10;
}
prev = newhead->next;
delete newhead;
return prev;
}
};
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* newhead = new ListNode(-1);
newhead->next = head;
ListNode* prev = newhead;
ListNode* cur = newhead->next;
ListNode* next = cur == nullptr ? nullptr : cur->next;
ListNode* nnext = next == nullptr ? nullptr : next->next;
while(cur && next)
{
prev->next = next;
next->next = cur;
cur->next = nnext;
prev = cur;
cur = prev->next;
next = cur == nullptr ? nullptr : cur->next;
nnext = next == nullptr ? nullptr : next->next;
}
prev = newhead->next;
delete newhead;
return prev;
}
};
3.重排链表
/**
* 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 reorderList(ListNode* head) {
if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
// 1.找到链表的中间结点 -- 快慢双指针
ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
// 2.将链表的slow->next后面的链表逆序组成一个新的链表
ListNode* head2 = new ListNode(-1);
ListNode* cur = slow->next;
slow->next = nullptr;
while(cur)
{
ListNode* next = cur->next;
cur->next = head2->next;
head2->next = cur;
cur = next;
}
// 3.将两个链表合并
ListNode* ret = new ListNode(-1);
ListNode* cur1 = head, *cur2 = head2->next;
ListNode* prev = ret;//记录一下尾节点
while(cur1)
{
//先放第一个链表
prev->next = cur1;
cur1 = cur1->next;
prev = prev->next;
if(cur2)
{
prev->next = cur2;
prev = prev->next;
cur2 = cur2->next;
}
}
delete head2;
delete ret;
}
};
4.合并 K 个升序链表
合并k个升序链表
方法一：
/**
* 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 {
struct cmp{
bool operator()(const ListNode* l1, const ListNode* l2)
{
return l1->val > l2->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
ListNode* head = new ListNode(-1);
//让所有的lists的头结点进入堆
for(auto list : lists)
if(list) heap.push(list);
//合并链表
ListNode* prev = head;
while(!heap.empty())
{
ListNode* t = heap.top();
heap.pop();
prev->next = t;
prev = t;
if(t->next) heap.push(t->next);
}
prev = head->next;
delete head;
return prev;
}
};
方法二：
/**
* 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* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
ListNode* merge(vector<ListNode*>& lists, int left, int right)
{
if(left > right) return nullptr;
if(left == right) return lists[left];
int mid = (left + right) >> 1;
ListNode* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid + 1, right);
return mergeTowList(l1, l2);
}
ListNode* mergeTowList(ListNode* l1, ListNode* l2)
{
if(l1 == nullptr) return l2;
if(l2 == nullptr) return l1;
ListNode head;
ListNode* prev = &head;
head.next = nullptr;
ListNode* cur1 = l1, *cur2 = l2;
while(cur1 && cur2)
{
if(cur1->val <= cur2->val)
{
prev = prev->next = cur1;
cur1 = cur1->next;
}
else
{
prev = prev->next = cur2;
cur2 = cur2->next;
}
}
if(cur1) prev->next = cur1;
if(cur2) prev->next = cur2;
return head.next;
}
};
5.K 个一组翻转链表
/**
* 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* reverseKGroup(ListNode* head, int k) {
// 1.先求出需要翻转几组
int n = 0;
ListNode* cur = head;
while(cur)
{
cur = cur->next;
n++;
}
n /= k;
ListNode* ret = new ListNode(-1);
ListNode* prev = ret;
cur = head;
for(int i = 0; i < n; i++)
{
ListNode* tmp = cur;
for(int j = 0; j < k; j++)
{
ListNode* next = cur->next;
cur->next = prev->next;
prev->next = cur;
cur = next;
}
prev = tmp;
}
prev->next = cur;
prev = ret->next;
delete ret;
return prev;
}
};
原文地址：https://blog.csdn.net/2301_78611726/article/details/143952868
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！