C++ | Leetcode C++题解之第143题重排链表

题目:

题解:

class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr) {
            return;
        }
        ListNode* mid = middleNode(head);
        ListNode* l1 = head;
        ListNode* l2 = mid->next;
        mid->next = nullptr;
        l2 = reverseList(l2);
        mergeList(l1, l2);
    }

    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    void mergeList(ListNode* l1, ListNode* l2) {
        ListNode* l1_tmp;
        ListNode* l2_tmp;
        while (l1 != nullptr && l2 != nullptr) {
            l1_tmp = l1->next;
            l2_tmp = l2->next;

            l1->next = l2;
            l1 = l1_tmp;

            l2->next = l1;
            l2 = l2_tmp;
        }
    }
};

相关推荐

最近更新

  1. mysql容器问题mbind: Operation not permitted

    2024-06-11 08:36:05       0 阅读
  2. NFS网络文件存储入门

    2024-06-11 08:36:05       0 阅读
  3. 小甲鱼——字典

    2024-06-11 08:36:05       0 阅读
  4. Scrapy与MongoDB的异步数据存储

    2024-06-11 08:36:05       0 阅读
  5. k8s及etcd的每日自动备份及故障时的还原脚本

    2024-06-11 08:36:05       0 阅读
  6. Android中球体碰撞代码分享-kotlin,入门版

    2024-06-11 08:36:05       0 阅读
  7. Non-zero exit code pycharm

    2024-06-11 08:36:05       0 阅读
  8. 电脑常用DOS命令

    2024-06-11 08:36:05       0 阅读
  9. React@16.x(25)useReducer

    2024-06-11 08:36:05       0 阅读
  10. 2024.6.14刷题记录-KMP记录

    2024-06-11 08:36:05       0 阅读

热门阅读

  1. 【Python】易错点——数组;列表;内存分配

    2024-06-11 08:36:05       4 阅读
  2. NLP--朴素贝叶斯

    2024-06-11 08:36:05       4 阅读
  3. vue基础

    vue基础

    2024-06-11 08:36:05      2 阅读
  4. 归并排序!

    2024-06-11 08:36:05       4 阅读
  5. 开源项目学习(6)---- CMake 可执行文件生成

    2024-06-11 08:36:05       3 阅读
  6. 如何发布自己的npm插件包

    2024-06-11 08:36:05       4 阅读
  7. 如何在WPS中加载EndNote X9插件

    2024-06-11 08:36:05       3 阅读