做视频播放网站 赚钱,wordpress 留言 插件,自己做的网站怎么在百度上搜到,一建报名资格条件这道题会联系到前面写的一篇文章----快慢指针相关经典问题。
重排链表
指针法 这道题乍一看#xff0c;好像有点难处理#xff0c;但如果仔细观察就会发现#xff0c;这道题是查找中间节点反转链表链表的合并问题#xff0c;具体细节有些不同#xff0c;这个在反装中间链…这道题会联系到前面写的一篇文章----快慢指针相关经典问题。
重排链表
指针法 这道题乍一看好像有点难处理但如果仔细观察就会发现这道题是查找中间节点反转链表链表的合并问题具体细节有些不同这个在反装中间链表时要从中间节点的下一个位置开始反装具体过程如下。 代码实现
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;
}
