首页 > 代码库 > 【Leetcode】Reorder List
【Leetcode】Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes‘ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
快慢指针找到链表中点，将链表分为两段，翻转后半段，再合并两个子链表。
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 void reorderList(ListNode *head) {12 if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {13 return;14 }15 ListNode *fast = head, *slow = head;16 while (fast->next && fast->next->next) {17 fast = fast->next->next;18 slow = slow->next;19 }20 fast = slow->next;21 slow->next = nullptr;22 fast = reverseList(fast);23 head = mergeList(head, fast);24 }25 private:26 ListNode * reverseList(ListNode *head) {27 ListNode dummy(-1);28 ListNode *p = &dummy;29 while (head) {30 ListNode *temp = head->next;31 head->next = p->next;32 p->next = head;33 head = temp;34 }35 return dummy.next;36 }37 38 ListNode *mergeList(ListNode *l1, ListNode *l2) {39 ListNode dummy(-1);40 ListNode *p = &dummy;41 while (l1) {42 p->next = l1;43 l1 = l1->next;44 p = p->next;45 if (l2) {46 p->next = l2;47 l2 = l2->next;48 p = p->next;49 }50 }51 return dummy.next;52 }53 };
【Leetcode】Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。