devbox
Guff_9hys
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++ 链表OJ_c++ oi 链表

作者：Guff_9hys | 2024-08-07 06:57:56

赞

踩

c++ oi 链表

目录

1、2. 两数相加

2、24. 两两交换链表中的节点

3、143. 重排链表

4、23. 合并 K 个升序链表

5、25. K 个一组翻转链表

解决链表题目常用方法：

1、画图
2、引入虚拟"头”结点

  • 便于处理边界情况
  • 方便我们对链表操作

3、大胆定义变量，减少连接节点时出现错误。

4、快慢双指针

  • 判环
  • 找链表中环的入口
  • 找链表中倒数第 n个结点

1、2. 两数相加

 思路：模拟相加，注意进位问题。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  14.         ListNode* newhead=new ListNode(0);
  15.         ListNode* cur1=l1,*cur2=l2;
  16.         ListNode* cur=newhead;
  17.         int c=0;//进位
  18.         while(cur1||cur2||c){
  19.             if(cur1){
  20.                 c+=cur1->val;
  21.                 cur1=cur1->next;
  22.             }
  23.             if(cur2){
  24.                 c+=cur2->val;
  25.                 cur2=cur2->next;
  26.             }
  27.             cur->next=new ListNode(c%10);
  28.             cur=cur->next;
  29.             c/=10;
  30.         }
  31.         cur=newhead->next;
  32.         delete newhead;
  33.         return cur;
  34.     }
  35. };

2、24. 两两交换链表中的节点

 思路：循环、迭代(模拟)。定义一个带有虚拟头结点的链表统计结果，接着定义出包括虚拟头结点在内和它后三个节点方便直接插入新链表。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* swapPairs(ListNode* head) {
  14.         if (head == nullptr || head->next == nullptr) {
  15.             return head;
  16.         }
  17.         ListNode* newHead = new ListNode(0);
  18.         newHead->next = head;
  19.         ListNode *prev = newHead, *cur = prev->next, *next = cur->next,
  20.                  *nnext = next->next;
  21.         while (cur && next) {
  22.             prev->next = next;
  23.             next->next = cur;
  24.             cur->next = nnext;
  25.             prev = cur;
  26.             cur = prev->next;
  27.             if (cur)
  28.                 next = cur->next;
  29.             if (next)
  30.                 nnext = next->next;
  31.         }
  32.         cur = newHead->next;
  33.         delete newHead;
  34.         return cur;
  35.     }
  36. };
  • 首先创建一个新的头节点newHead，其值为0，并将其指向原链表的头节点head。
  • 使用指针prev指向newHead，指针cur指向prev的下一个节点（即原链表的头节点），指针next指向cur的下一个节点，指针nnext指向next的下一个节点。
  • 进入循环，条件是cur和next都不为空。在循环中：
    • 将prev的next指针指向next，实现交换相邻节点。
    • 将next的next指针指向cur，完成节点交换。
    • 将cur的next指针指向nnext，恢复链表连接。
    • 更新prev为cur，cur为prev的下一个节点，next为cur的下一个节点，nnext为next的下一个节点。
  • 循环结束后，重新定位cur指向新链表的头部，即newHead的下一个节点。
  • 删除创建的头节点newHead，并返回交换后链表的头节点cur。

3、143. 重排链表

 思路：快慢双指针找到中间节点，逆序后半部分，利用双指针合并两个链表。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     void reorderList(ListNode* head) {
  14.         if (head == nullptr || head->next == nullptr ||
  15.             head->next->next == nullptr) {
  16.             return;
  17.         }
  18.         ListNode *slow = head, *fast = head;
  19.         while (fast && fast->next) {
  20.             slow = slow->next;
  21.             fast = fast->next->next;
  22.         }
  23.         ListNode* rhead = new ListNode(0);
  24.         ListNode* cur = slow->next;//逆序不要中间节点
  25.         slow->next = nullptr;//分离逆序部分
  26.         while (cur) {
  27.             ListNode* next = cur->next;
  28.             cur->next = rhead->next;
  29.             rhead->next = cur;
  30.             cur = next;
  31.         }
  32.         ListNode *cur1 = head, *cur2 = rhead->next;
  33.         ListNode* ret = new ListNode(0);
  34.         ListNode* prev = ret;
  35.         while (cur1) {
  36.             prev->next = cur1;
  37.             cur1 = cur1->next;
  38.             prev = prev->next;
  39.             if (cur2) {
  40.                 prev->next = cur2;
  41.                 cur2 = cur2->next;
  42.                 prev = prev->next;
  43.             }
  44.         }
  45.         delete rhead;
  46.         delete ret;
  47.     }
  48. };

4、23. 合并 K 个升序链表

 思路：把所有的头结点放进⼀个⼩根堆（使用优先级队列实现）中，这样就能快速的找到每次 K 个链表中最⼩的元素是哪个。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     struct cmp {
  14.         bool operator()(const ListNode* a, const ListNode* b) {
  15.             return a->val > b->val;
  16.         }
  17.     };
  18.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  19.         priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
  20.         for (auto l : lists) {
  21.             if (l)
  22.                 heap.push(l);
  23.         }
  24.         ListNode* ret = new ListNode(0);
  25.         ListNode* prev = ret;
  26.         while (!heap.empty()) {
  27.             ListNode* t = heap.top();
  28.             heap.pop();
  29.             prev->next = t;
  30.             prev = t;
  31.             if (t->next)
  32.                 heap.push(t->next);
  33.         }
  34.         prev = ret->next;
  35.         delete ret;
  36.         return prev;
  37.     }
  38. };
  1. 定义一个比较结构体cmp，用于比较两个节点的值大小，确保优先级队列是一个最小堆。
  2. 遍历输入的链表数组lists，将每个链表的头节点（如果不为空）加入到优先级队列heap中。
  3. 创建一个哑节点ret，它将作为返回的链表的头节点的前驱，用于简化链表操作。同时，使用一个指针prev来跟踪当前链表的最后一个节点。
  4. 当heap不为空时，循环执行以下操作：
    • 从heap中取出最小值节点t（即优先级队列的顶部元素），这是当前所有链表头节点中值最小的节点。
    • 将prev的next指向t，将t接入到当前构建的链表中。
    • 更新prev指向t，即将prev移动到链表的最末端。
    • 如果t还有下一个节点（t->next不为空），则将这个下一个节点加入到heap中，以便继续参与后续的比较和选择过程。
  5. 循环结束后，所有输入的链表已经完全合并到了由ret->next开始的链表中。
  6. 在返回结果之前，首先保存ret->next到一个临时变量prev（这里重新使用prev变量来简化代码，其实是返回链表的头节点），然后删除哑节点ret。
  7. 返回prev，即合并后的链表的头节点。

思路二：递归/分治 

  1. class Solution {
  2. public:
  3.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  4.         return merge(lists, 0, lists.size() - 1);
  5.     }
  6.  
  7.     ListNode* merge(vector<ListNode*>& lists, int left, int right) {
  8.         int mid = left + right >> 1;
  9.         if (left > right)
  10.             return nullptr;
  11.         if (left == right)
  12.             return lists[left]; // 只有一个链表
  13.  
  14.         ListNode* l1 = merge(lists, left, mid);
  15.         ListNode* l2 = merge(lists, mid + 1, right);
  16.  
  17.         return mergeTwoList(l1, l2);
  18.     }
  19.  
  20.     ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
  21.         if (l1 == nullptr)
  22.             return l2;
  23.         if (l2 == nullptr)
  24.             return l1;
  25.  
  26.         ListNode head;
  27.         ListNode *cur1 = l1, *cur2 = l2, *prev = &head;
  28.         head.next = nullptr;
  29.  
  30.         while (cur1 && cur2) {
  31.             if (cur1->val <= cur2->val) {
  32.                 prev = prev->next = cur1;
  33.                 cur1 = cur1->next;
  34.             } else {
  35.                 prev = prev->next = cur2;
  36.                 cur2 = cur2->next;
  37.             }
  38.         }
  39.  
  40.         if (cur1)
  41.             prev->next = cur1;
  42.         if (cur2)
  43.             prev->next = cur2;
  44.  
  45.         return head.next;
  46.     }
  47. };

5、25. K 个一组翻转链表

 思路：先求出需要逆序的组数n，重复n次长度为k的链表逆序，通过头插到新链表实现逆序，每头插k个元素后更新头插位置。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* reverseKGroup(ListNode* head, int k) {
  14.         int n = 0;
  15.         ListNode* cur = head;
  16.         while (cur) {
  17.             cur = cur->next;
  18.             n++;
  19.         }
  20.         n /= k;
  21.         ListNode* newhead = new ListNode(0);
  22.         ListNode* prev = newhead;
  23.         cur = head;
  24.         for (int i = 0; i < n; i++) {
  25.             ListNode* tmp = cur;
  26.             for (int j = 0; j < k; j++) {
  27.                 ListNode* next = cur->next;
  28.                 cur->next = prev->next;
  29.                 prev->next = cur;
  30.                 cur = next;
  31.             }
  32.             prev = tmp;
  33.         }
  34.         prev->next = cur;
  35.         cur = newhead->next;
  36.         delete newhead;
  37.         return cur;
  38.     }
  39. };
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/941376
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号