首页 > 代码库 > [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}.
思路：找到中间节点，将链表的后半部分就地逆置。然后插入到前半部分。
时间复杂度O(n),空间复杂度O(1) 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 == NULL || head->next == NULL || head->next->next == NULL) 13 return;14 15 int length = 0;16 for (ListNode *pter = head; pter != NULL; pter = pter->next) {17 ++length;18 }19 20 int half_length = 1;21 ListNode *half = head;22 while (half_length < (length / 2)) {23 ++half_length;24 half = half->next;25 }26 27 //reverse28 ListNode *pter = half->next;29 half->next = NULL;30 while (pter != NULL) {31 ListNode *next_node = pter->next;32 pter->next = half->next;33 half->next = pter;34 pter = next_node;35 }36
37 ListNode *pter2 = head;38 pter = half->next;39 while (pter2 != half) {40 ListNode *next_node = pter->next;41 half->next =next_node;42 pter->next = pter2->next;43 pter2->next = pter;44 pter2 = pter2->next->next;45 pter = next_node;46 }47 }48 };
[LeetCode] Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。