链表题目练习----重排链表

这道题会联系到前面写的一篇文章----快慢指针相关经典问题。

重排链表

指针法

这道题乍一看，好像有点难处理，但如果仔细观察就会发现，这道题是查找中间节点+反转链表+链表的合并问题，具体细节有些不同，这个在反装中间链表时，要从中间节点的下一个位置开始反装，具体过程如下。

代码实现：

typedef struct ListNode Node;Node* ReverseList(struct ListNode* head)
{Node* cur = head;Node* n1 = NULL, *n2 = head, *n3 = head->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}Node* MidList(struct ListNode* head)
{Node* fast = head, *slow = head;while (fast && fast->next){slow = slow->next;if(fast)fast = fast->next->next;}return slow;
}void reorderList(struct ListNode* head)
{if (head == NULL || head->next == NULL || head->next->next == NULL){return;}Node* cur = head, *mid = MidList(head);Node* rev = ReverseList(mid->next);mid->next = NULL;Node* tmp1 = cur, *tmp2 = rev;while (cur && rev){tmp1 = cur->next;tmp2 = rev->next;cur->next = rev;cur = tmp1;rev->next = cur;rev = tmp2;}
}

数组法

数组法就是利用数组直接存储每个节点，然后直接插入排序。首先开辟一个类型为struct ListNode*的数组存储每个节点，然后就重排。

这个我们直接上代码

typedef struct ListNode Node;void reorderList(struct ListNode* head)
{//如果是这种情况下，重排的结果与原链表相同，我们直接返回if (head == NULL || head->next == NULL || head->next->next == NULL){return;}//开辟数组Node* arr[40001];Node* cur = head;int n = 0;//存储每个节点的值while(cur){arr[n++] = cur;cur = cur->next;}//开始重排int i = 0, j = n - 1;while (i < j){//直接在原链表中操作，不用担心覆盖问题，因为这些值在数组中均有存储arr[i]->next = arr[j];i++;if (i == j){break;}arr[j]->next = arr[i];j--;}//最后不要忘了把重排后的最后一个位置置为空，防止成环//这里直接置最后i位置的值为空，我们等会画图解释arr[i]->next = NULL;
}