LeetCode-143. Reorder List

LeetCode-143. 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 may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

题解：

一种易于理解的算法：

每次选择第一个和最后一个结点拼装，然后连接剩下的中间链，类推下去：

时间复杂度是On!

class Solution {public: void reorderList(ListNode* head) { if (!head || !head->next) return; ListNode *p = head; ListNode *pre = NULL; while (p->next) { pre = p; p = p->next; } pre->next = NULL; ListNode *next = head->next; head->next = p; p->next = next; reorderList(next); }};

另一种双指针找出前半段和后半段，再将后半段翻转，依次拼装到前半段中间，这里使用三指针法反转链表。

时间复杂度是On

class Solution {public: ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } else { ListNode *p1 = head, *p2 = head->next, *p3; while (p2 != NULL) { p3 = p2->next; p2->next = p1; p1 = p2; p2 = p3; } head->next = NULL; return p1; } } void reorderList(ListNode* head) { if (head == NULL || head->next == NULL) { return; } ListNode *p = head, *q = head; while (q != NULL && q->next != NULL) { p = p->next; q = q->next->next; } ListNode *r = reverseList(p->next); p->next = NULL; p = head; while(r != NULL && p != NULL && p->next != NULL) { q = r; r = r->next; q->next = p->next; p->next = q; p = p->next->next; } }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。