学习日记【LeetCode】143. 重排链表

【LeetCode】143. 重排链表

一、题目内容

给定一个单链表 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.找到原链表的中点。 我们可以使用快慢指针来 O(N)地找到链表的中间节点。 2.将原链表的右半端反转。 我们可以使用迭代法实现链表的反转。 3.将原链表的两端合并。 因为两链表长度相差不超过 1，因此直接合并即可。 时间复杂度：O(N)，其中 N 是链表中的节点数。 空间复杂度：O(1)。 太强了！！我的代码都是什么鬼

四、作答

我的代码

struct ListNode* reverseList(struct ListNode* ls) { struct ListNode* r = NULL; struct ListNode* q = NULL; struct ListNode* p = ls; while (p != NULL) { q = p->next; p->next = r; r = p; p = q; } return r; } void reorderList(struct ListNode* head) { if(head == NULL) return; struct ListNode* p = head; while(p->next != NULL) { p->next = reverseList(p->next); p = p->next; } }//就是思路一

错处与修改

第一次交的时候忘了这句：

if(head == NULL) return;

其他都没什么问题了。

五、官方或网友解答

思路二：

void reorderList(struct ListNode* head) { if (head == NULL) { return; } struct ListNode* vec[40001]; struct ListNode* node = head; int n = 0; while (node != NULL) { vec[n++] = node; node = node->next; } int i = 0, j = n - 1; while (i < j) { vec[i]->next = vec[j]; i++; if (i == j) { break; } vec[j]->next = vec[i]; j--; } vec[i]->next = NULL; } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路三：

struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast->next != NULL && fast->next->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev = NULL; struct ListNode* curr = head; while (curr != NULL) { struct ListNode* nextTemp = curr->next; curr->next = prev; prev = curr; curr = nextTemp; } return prev; } void mergeList(struct ListNode* l1, struct ListNode* l2) { struct ListNode* l1_tmp; struct ListNode* l2_tmp; while (l1 != NULL && l2 != NULL) { l1_tmp = l1->next; l2_tmp = l2->next; l1->next = l2; l1 = l1_tmp; l2->next = l1; l2 = l2_tmp; } } void reorderList(struct ListNode* head) { if (head == NULL) { return; } struct ListNode* mid = middleNode(head); struct ListNode* l1 = head; struct ListNode* l2 = mid->next; mid->next = NULL; l2 = reverseList(l2); mergeList(l1, l2); } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

六、备注