Leetcode 143. Reorder List | | Leetcode 143. Reorder List 文章作者:Tyan博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: void reorderList(ListNode* head) { if(!head) { return; } ListNode* p1 = head; ListNode* p2 = head; while(p2 && p2->next) { p1 = p1->next; p2 = p2->next->next; } ListNode* left = head; ListNode* right = reverseList(p1->next); p1->next = nullptr; ListNode* new_head = new ListNode(0); ListNode* current = new_head; while(left && right) { current->next = left; left = left->next; current = current->next; current->next = right; current = current->next; right = right->next; } current->next = left?left:right; head = new_head->next; } private: ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* next = nullptr; ListNode* current = head; while(current) { next = current->next; current->next = pre; pre = current; current = next; } return pre; }}; Reference https://leetcode.com/problems/reorder-list/description/ 如果有收获,可以请我喝杯咖啡! 赏 微信打赏 支付宝打赏