给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
方法1:线性表,存储所有结点
void reorderList(ListNode* head)
{
if (!head) return;
ListNode * node = head;
vector<ListNode *> Nodes;
while(node)
{
Nodes.emplace_back(node);
node = node->next;
}
int i = 0;
int j = Nodes.size()-1;
while(i < j)
{
Nodes[i]->next = Nodes[j];
++i;
if (i == j)
break;
Nodes[j]->next = Nodes[i];
--j;
}
Nodes[i]->next = nullptr;
}
/*
时间复杂度:O(N),其中 N 是链表中的节点数。
空间复杂度:O(N),其中 N 是链表中的节点数。主要为线性表的开销。
*/
方法2:链表中点+翻转链表+合并链表
ListNode * middleNode(ListNode *node)
{
ListNode * fast = node;
ListNode * slow = node;
while(fast->next && fast->next->next) // fast->next->next很重要
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode * reverseList(ListNode *node) // 翻转链表
{
ListNode *prv = nullptr;
ListNode *curr = node;
while(curr != nullptr)
{
ListNode * tmp = curr->next;
curr->next = prv;
prv = curr;
curr = tmp;
}
return prv;
}
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;
}
}
void reorderList(ListNode* head)
{
if (!head) return;
ListNode * middle_node = middleNode(head);
ListNode * l1 = head;
ListNode * l2 = middle_node->next;
middle_node->next = nullptr;
l2 = reverseList(l2);
mergeList(l1, l2);
}
欢迎交流,批评指正!