LeetCode Q143: Reorder List

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

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	void reorderList(ListNode* head) {
	if(head==NULL||head->next==NULL)
	return;
	//Get middle of list
	ListNode* mid=head;
	ListNode* fast=head->next;
	while(fast && fast->next){
	mid=mid->next;
	fast=fast->next->next;
	}
	// Reverse 2nd list
	ListNode* head2=mid->next;
	mid->next=NULL;
	ListNode* last=head2;
	ListNode* p=head2->next;
	last->next=NULL;
	while(p!=NULL){
	ListNode* pnext=p->next;
	p->next=last;
	last=p;
	p=pnext;
	}
	head2=last;
	//Merge two lists;
	while(head!=NULL&&head2!=NULL){
	ListNode* hnext=head->next;
	ListNode* h2next=head2->next;
	head->next=head2;
	head2->next=hnext;
	head=hnext;
	head2=h2next;
	}
	}
	};

view raw Q143ReorderList.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	void reorderList(ListNode* head) {
	if(head==NULL||head->next==NULL)
	return;
	//Get middle of list
	ListNode* p1=head;
	ListNode* p2=head;
	while(p2->next!=NULL&&p2->next->next!=NULL){
	p1=p1->next;
	p2=p2->next->next;
	}
	p2=p1->next;
	p1->next=NULL;
	// Reverse 2nd list
	ListNode* pre=NULL;
	ListNode* next=p2->next;
	while(next!=NULL){
	p2->next=pre;
	pre=p2;
	p2=next;
	next=next->next;
	}
	p2->next=pre;
	//Merge two lists
	p1=head;
	while(p1!=NULL&&p2!=NULL){
	ListNode* tmp1 = p1->next;
	ListNode* tmp2 = p2->next;
	p1->next = p2;
	p2->next = tmp1;
	p1 = tmp1;
	p2 = tmp2;
	}
	}
	};

view raw Q143Rnd2.cpp hosted with ❤ by GitHub