143. Reorder List(Leetcode每日一题-2020.10.20)

本文主要是介绍143. Reorder List(Leetcode每日一题-2020.10.20)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example1

Given 1->2->3->4, reorder it to 1->4->2->3.

Example2

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Solution

/*** 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:void reorderList(ListNode* head) {if(!head || !head->next || !head->next->next)return;//找到中间节点的前一个节点int len = 0;ListNode *cur = head;while(cur){++len;cur = cur->next;}len =len /2 -1;cur = head;while(len){--len;cur = cur->next;}//打断链表，翻转后半段ListNode *one_cur = head;ListNode *tmp = cur->next;cur->next = NULL;ListNode *two_cur = reverse(tmp);//printList(one_cur);//printList(two_cur);ListNode dummy;head = &dummy;while(one_cur || two_cur){if(one_cur){head->next = one_cur;head = head->next;one_cur = one_cur->next;}if(two_cur){head->next = two_cur;head = head->next;two_cur = two_cur->next;}}head = dummy.next;}/*void printList(ListNode *head){ListNode *cur = head;while(cur){cout<<cur->val<<"->";cur = cur->next;}cout<<"nil"<<endl;}*/ListNode *reverse(ListNode *head){if(!head || !head->next)return head;ListNode *newHead = reverse(head->next);head->next->next = head;head->next = NULL;return newHead;}
};