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; } };