算法练习——链表
一：两数相加题目要求：
https://i-blog.csdnimg.cn/direct/579c0b3e417746ef8d7dafd403f24730.png
解题思路：
思路：注意进位即可
实今世码：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* cur1 = l1, * cur2 = l2;
ListNode* phead = new ListNode(0);
ListNode* cur = phead;
int sum = 0;
while(cur1 || cur2 || sum) {//除了两个链表中的数外，还要考虑进位，只要存在进位就要加
if(cur1) {
sum += cur1->val;
cur1 = cur1->next;
}
if(cur2) {
sum += cur2->val;
cur2 = cur2->next;
}
cur->next = new ListNode(sum%10);
cur = cur->next;
sum /= 10;
}
ListNode* tmp = phead->next;
delete phead;
return tmp;
} 二：两两交换链表中的节点
题目要求：
https://i-blog.csdnimg.cn/direct/091a60942cdd4cf4bde53d6bccf63ab8.png
解题思路：
思路：通过两个指针遍历链表，遍历的同时，将指针指向的节点按照顺序头插入新的节点中
实今世码：
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr) {
return head;
}
ListNode* prev = head, *cur = head->next;
ListNode* phead = new ListNode(0);
ListNode* tmp = phead;
while(prev && cur) {
tmp->next = new ListNode(cur->val);
tmp = tmp->next;
tmp->next = new ListNode(prev->val);
tmp = tmp->next;
prev = cur->next;
if(prev) {
cur = prev->next;
}
}
tmp->next = prev;
tmp = phead->next;
delete phead;
return tmp;
} 三：重排链表
题目要求：
https://i-blog.csdnimg.cn/direct/c34eec3cdecd4054a1b1c05f3eb8fe20.png
解题思路：
思路：
①通过快慢指针找到中心节点，此时慢指针将整个链表分成两段
②断开前一段，以及翻转后一段
③归并两个链表
实今世码：
ListNode * Reverse(ListNode * head) {
ListNode* phead = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* next = cur->next;
cur->next = phead;
phead = cur;
cur = next;
}
return phead;
}
//思路：找到中间节点并翻转，然后合并两个链表
void reorderList(ListNode * head) {
//排除边界条件
if (head->next == nullptr || head->next->next == nullptr) {
return;
}
//找中间节点
ListNode* fast = head,* slow = head,* tmp = head;
while (fast && fast->next) {
fast = fast->next->next;
tmp = slow;
slow = slow->next;
}
//断开前一个链表
tmp->next = nullptr;
ListNode* cur1 = head;
ListNode* cur2 = Reverse(slow);//翻转第二个链表
ListNode* phead = new ListNode(0);
ListNode* cur = phead;
//合并两个链表
while (cur1 || cur2) {
if(cur1) {
ListNode* next = cur1->next;
cur->next = cur1;
cur = cur1;
cur1 = next;
}
if(cur2) {
ListNode* next = cur2->next;
cur->next = cur2;
cur = cur2;
cur2 = next;
}
}
head = phead->next;;
delete phead;
} 四：归并K个升序链表
题目要求：
https://i-blog.csdnimg.cn/direct/de227b561fbc4326be92fa1a1b762b00.png
解题思路：
思路：借助优先级队列来辅助解题
①将vector中，链表的头节点建成小堆，此时堆顶数据为最小值
②取堆顶数据，并用变量cur记录，再出堆顶数据，此时cur为vector中，某一链表的头节点
③将cur链接到一个新的链表中，同时判断cur->next 节点是否为空，若不为空，将其插入堆中，重新建堆，包管堆顶始终是最小值，当堆为空时，表现已经遍历完全部链表此时循环竣事。
实今世码：
struct com {
//vector中默认的排序不满足题目要求，所以得自己实现
bool operator()(const ListNode* x1, const ListNode* x2) {
return x1->val > x2->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*,vector<ListNode*>,com> heap;
//将vector中，每个链表的头节点建堆
for(auto l : lists) {
if(l) heap.push(l);
}
ListNode* phead = new ListNode(0);
ListNode* cur = phead;
while(!heap.empty()) {
cur->next = heap.top();//堆顶元素其实就是一个节点，且该节点为最小值，赋值给cur
heap.pop();//出堆顶，避免重复
cur = cur->next;
if(cur->next) {//如果vector中 某个链表仍存在下一个节点，则插入进堆中，重新建堆，确保堆顶仍为最小节点
heap.push(cur->next);
}
}
return phead->next;
} 五：K个一组翻转链表
题目要求：
https://i-blog.csdnimg.cn/direct/d111f8d6bb844b53bf64b1d4f0b781f8.png
解题思路：
思路：
①：遍历链表，统计一个有几个节点total，n = total / k 得到需要翻转n次
②：创建一个链表头phead，定义两个链表变量cur、prev，令 cur = head, prev = phead; 创建一个链表遍历 next = cur->next;如图所示：
https://i-blog.csdnimg.cn/direct/911fac9b5ae34b9f8bf0c0208d2ec9b8.png
③：通过两次循环，外循环为统共翻转的次数，内循环为每次翻转时，需要翻转的数的个数。在进行内循环前，定义一个链表遍历 tmp = cur，如图所示：
https://i-blog.csdnimg.cn/direct/c5d7df824bfc48489d3ef248fefcd384.png
④：在内循环中，我们进行头插操作
for(int j = 0; j < k; j++) {
ListNode* next = cur->next;
cur->next = prev->next;
prev->next = cur;
cur = next;
{当内循环一轮竣事时，此时指针指向如图所示：
https://i-blog.csdnimg.cn/direct/9692e23bb6964872aa63b8961895ba95.png
⑤：此时我们需将prev更新至tmp位置，以满足下一次循环可以或许进行头插操作，下一次内循环开始前，又会将tmo更新至cur位置，这样第二次循环竣事时，同样将prev的位置更新至tmp，开始第三次头插，直至外循环竣事。如图所示
https://i-blog.csdnimg.cn/direct/c556a1b4548c47f0b8ca88d8d8215835.png
⑥：当外循环竣事时，此时判断cur是否为空，若不为空，则将后续数据链接到prev反面。
实今世码：
ListNode* reverseKGroup(ListNode* head, int k) {
if(head->next == nullptr) {
return head;
}
ListNode* cur = head;
int total = 0;
while(cur) {
total++;
cur = cur->next;
}
int n = total / k;
ListNode* phead = new ListNode(0);
cur = head;
ListNode *prev = phead;
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;
}
if(cur) {
prev->next = cur;
}
ListNode* ret =phead->next;
delete phead;
return ret;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]