LeetCode Reorder List

struct ListNode {

	int val;

	ListNode *next;

	ListNode(int x) : val(x), next(NULL) {}

};

class Solution {

public:

	void reorderList(ListNode* head)

	{

		if(head == nullptr) return;

		int size = 0;

		ListNode *ptr = head;

		while(ptr != nullptr)

		{

			size++;

			ptr = ptr->next;

		}

		if(size <= 2) return;

		int breakpoint = (size + 1) / 2;

		int i = 0;

		ptr = head;

		while( i++ < breakpoint)

		{

			ptr = ptr->next;

		}

		ListNode *ptr2 = head;

		while(ptr2!= nullptr && ptr2->next != ptr)

			ptr2 = ptr2->next;

		if(ptr2 != nullptr)

			ptr2->next = nullptr;

		ListNode* newheadof2ndPart = reverseLinkedList(ptr);

		ptr = head;

		for(i = 0; i< breakpoint && ptr != nullptr && newheadof2ndPart != nullptr; i++)

		{

			ListNode*ptmp = ptr->next;

			ListNode*pnextnewhead = newheadof2ndPart->next;

			ptr -> next = newheadof2ndPart;

			newheadof2ndPart->next = ptmp;

			ptr = ptmp;

			newheadof2ndPart = pnextnewhead;

		}

	}

	ListNode* reverseLinkedList(ListNode* head)

	{

		if(head == nullptr) return nullptr;

		ListNode* newhead = reverseLinkedList(head->next);

		if(head-> next != nullptr)

		{

			head->next->next = head; //Error, 一定要搞清楚到底是哪个next哦

		}

		if(newhead == nullptr) newhead = head;

		head->next = nullptr;

		return newhead;

	}

};