每日一题《leetcode--143.重排链表》

https://leetcode.cn/problems/reorder-list/

---

这道题我们可以用两种方法

第一种：用数组存储该链表，然后通过访问数组下标的方式来改变该链表的排列方式。 

void reorderList(struct ListNode* head) {第一种方法：用线性表存储该链表if(head == NULL){return;}struct ListNode* node = head;struct ListNode* vec[500001];int n = 0; while(node){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;
}

 

---

第二种方法：我们可以用三个端口函数来实现

1. 找到原链表的中点

   我们可以使用快慢指针来 O(N)O(N)O(N) 地找到链表的中间节点。

2. 将原链表的右半端反转

   我们可以使用迭代法实现链表的反转。

3. 将原链表的两端合并。

   因为两链表长度相差不超过 111，因此直接合并即可。

 //寻找中间结点
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow = head;struct ListNode* fast = head;while(fast->next && fast->next->next){slow = slow->next;fast = fast->next->next;}return slow;
}//反转链表
struct ListNode* ReverseList(struct ListNode* head)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;while(cur){struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;
}//合并链表
void mergeList(struct ListNode* l1, struct ListNode* l2)
{while(l1 && l2){struct ListNode* Node1 = l1->next;struct ListNode* Node2 = l2->next;l1->next = l2;l1 = Node1;l2->next = l1;l2 = Node2;}}
void reorderList(struct ListNode* head) {//第二种方法：找到中间结点，将原链表的右半段给反转，最后将原链表的两端合并if(head == NULL){return;}struct ListNode* mid = middleNode(head);struct ListNode* l1 = head;//原链表右半段的头struct ListNode* l2 = mid->next;//把合并链表后的最后一个节点的next设为空mid->next = NULL;l2 = ReverseList(l2); mergeList(l1, l2);  
}