算法练习——链表
一：两数相加
题目要求：
解题思路：
思路：注意进位即可
实现代码：
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;
}二：两两交换链表中的节点
题目要求：
解题思路：
思路：通过两个指针遍历链表，遍历的同时，将指针指向的节点按照顺序头插入新的节点中
实现代码：
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;
}三：重排链表
题目要求：
解题思路：
思路：
①通过快慢指针找到中间节点，此时慢指针将整个链表分成两段
②断开前一段，以及翻转后一段
③合并两个链表
实现代码：
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个升序链表
题目要求：
解题思路：
思路：借助优先级队列来辅助解题
①将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个一组翻转链表
题目要求：
解题思路：
思路：
①：遍历链表，统计一个有几个节点total，n = total / k 得到需要翻转n次
②：创建一个链表头phead，定义两个链表变量cur、prev，令 cur = head, prev = phead; 创建一个链表遍历 next = cur->next;如图所示：
③：通过两次循环，外循环为总共翻转的次数，内循环为每次翻转时，需要翻转的数的个数。在进行内循环前，定义一个链表遍历 tmp = cur，如图所示：
④：在内循环中，我们进行头插操作
for(int j = 0; j < k; j++) { ListNode* next = cur->next; cur->next = prev->next; prev->next = cur; cur = next; {当内循环一轮结束时，此时指针指向如图所示：
⑤：此时我们需将prev更新至tmp位置，以满足下一次循环能够进行头插操作，下一次内循环开始前，又会将tmo更新至cur位置，这样第二次循环结束时，同样将prev的位置更新至tmp，开始第三次头插，直至外循环结束。如图所示
⑥：当外循环结束时，此时判断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;
}原文地址：https://blog.csdn.net/m0_51952310/article/details/145202693
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！