LeetCode 143.重排链表

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

        分析题目后我们可以直接进行模拟实现。

        具体用到的就是我们之前的知识的结合，首先使用快慢指针找到链表的中间结点。然后将后半段链表给翻转一下，然后再让这两个链表进行合并。

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:// 找出链表中点ListNode* middleListNode(ListNode* head){ListNode* slow=head,* fast=head;while(fast->next!=nullptr&&fast->next->next!=nullptr){slow=slow->next;fast=fast->next->next;}return slow;}// 翻转链表ListNode* reverselist(ListNode* l){ListNode* cur=l;ListNode* prev=nullptr;while(cur){ListNode* next=cur->next;cur->next=prev;prev=cur;cur=next;}return prev;}// 合并链表void reorderList(ListNode* head) {if(head==nullptr||head->next==nullptr||head->next->next==nullptr) return;ListNode* midnode=middleListNode(head);ListNode* l1=head;ListNode* l2=midnode->next;midnode->next=nullptr;l2=reverselist(l2);ListNode* phead=new ListNode(0);ListNode* temp=phead;while(l1||l2){if(l1){temp->next=l1;l1=l1->next;temp=temp->next;}if(l2){temp->next=l2;l2=l2->next;temp=temp->next;}}// ListNode* l1next;// ListNode* l2next;// while(l1!=nullptr&&l2!=nullptr)// {//     l1next=l1->next;//     l2next=l2->next;//     l1->next=l2;//     l1=l1next;//     l2->next=l1;//     l2=l2next;// }}
};