---

前言

题目如下：
重排链表(点我）

一、线性表

因为链表不能下标访问元素，所以我们不能随机访问链表中的元素，因此我们采用数组来存储链表中的每一个元素。利用线性表可以随机访问元素的特点，可以轻松解决该题目。
具体代码如下：

void reorderList(struct ListNode* head) {if (head == NULL) {return;}struct ListNode* vec[40001];struct ListNode* node = head;int n = 0;while (node != NULL)//遍历将链表每个节点存储于数组vec中 {vec[n++] = node;node = node->next;}int i = 0, j = n - 1;while (i < j)//按照题目所述下标访问规律进行链接{vec[i]->next = vec[j];i++;if (i == j)//当i==j时退出循环{break;}vec[j]->next = vec[i];j--;}vec[i]->next = NULL;
}
代码来源：leetcode官方题解

空间复杂度0(n) 时间复杂度0(1)
这种方法还是非常好想的

二、寻找链表中点 + 链表逆序 + 合并链表

想进一步优化，必须要熟悉快慢指针找中间节点，链表逆序等，下面有这些题目的链接供大家参考：
链表的中间节点
反转链表
具体步骤：
1.找到原链表的中间节点
2. 将中间节点的后半部分反转
3. 按循序将二个链表交叉链接
过程如动图：
具体代码如下：

struct ListNode* getMid(struct ListNode* head)//获取中间节点
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}
struct ListNode* Swap(struct ListNode* head)//逆序
{struct ListNode* prev = NULL;struct ListNode* cur = head;struct ListNode* next = head->next;while (cur){cur->next = prev;prev = cur;cur = next;if (next != NULL){next = next->next;}}return prev;
}
void reorderList(struct ListNode* head) {if (head == NULL){return;}if(head->next==NULL){return;}struct ListNode* mid = getMid(head);struct ListNode* cur = head;struct ListNode* prev = head;while (cur != mid){prev = cur;cur = cur->next;}prev->next = NULL;struct ListNode* p2 = Swap(mid);struct ListNode* p1 = head;struct ListNode* next1 = p1;struct ListNode* next2 = p2;cur = head;int n = 1;while (next1 != NULL){if (n % 2 != 0){next1 = cur->next;cur->next = next2;cur = cur->next;}else{next2 = cur->next;cur->next = next1;cur = cur->next;}n++;}
}

总结

以上就是重组链表的全部内容希望对大家有帮助!