LeetCode Reorder List 新鲜出炉问题的解答

Reorder List

Given a singly linked listL:L₀→L₁→…→L_n-1→L_n,
reorder it to:L₀→L_n→L₁→L_n-1→L₂→L_n-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}.

终于调试出来了，考的是链表的操作，要对链表的操作非常清楚，否则也是很难调试的，总会有问题出来。我完成的时候50个accepted左右，提交的有400多。差不多10%多一点的通过率，看来还是有一定难度的了。

我的思路是：

1 计算链表长度

2 计算需要插入前面的元素，然后转置这些元素

3 用中间一个共有的元素作为结束点，循环插入。

不是很优化的算法，不过也accepted了。暂时没有想到更加优化的算法。

下面是程序。

class Solution {
public:
	void reorderList(ListNode *(&head)) 
	{
		if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
		int n = listCount(head);
		int r = (n-1)/2;
		int i = 0;
		ListNode *pre = head;
		ListNode *cur = head;
		while (cur->next)
		{
			cur=cur->next;
			if(i<r) i++;
			else pre=pre->next;
		}
		ListNode *tail;
		tail = reverseList(pre);
		ListNode *ph = head;

		while (ph != pre)
		{
			insertBack(ph, tail);
		}
		ph->next = nullptr;
	}

	void insertBack(ListNode *(&head), ListNode *(&back))
	{
		ListNode *temp = back->next;
		back->next=head->next;
		head->next=back;
		head=back->next;
		back = temp;
	}


	ListNode* reverseList(ListNode *(&head))
	{
		if(head == nullptr || head->next == nullptr) return nullptr;
		ListNode *pre = head->next;
		ListNode *cur = head->next->next;
		ListNode *post;
		pre->next = head;
		if(cur == nullptr)
			return pre;
		
		if(cur->next != nullptr)
			post = cur->next;
		else
		{
			cur->next = pre;
			return cur;
		} 

		cur->next = pre;
		while(post != nullptr)
		{
			pre = cur;
			cur = post;
			post = post->next;
			cur->next = pre;
		}
		return cur;
	}

	int listCount(ListNode *head)
	{
		int n = 0;
		ListNode *ph = head;
		while (ph!=nullptr)
		{
			ph = ph->next;
			n++;
		}
		return n;
	}
};

算法很多都能看明白，但是真正动手又是另外一回事了。

4到5星级难度。

考点：

1 反正链表

2 两链表插入节点

3 找到特定节点

//2014-2-19 update
	void reorderList(ListNode *head)
	{
		int len = getLength(head);
		if (len < 3) return;
		int m = (len-1)>>1;
		ListNode *pre = head->next;
		ListNode *tail = pre->next;

		while (--m>0) tail = tail->next;
		while (tail->next)
		{
			pre = pre->next;
			tail = tail->next;
		}
		reverseList(pre);

		tail = pre->next;
		pre->next = nullptr;
		intertwinedList(head, tail);
	}
	void intertwinedList(ListNode *&h1, ListNode *h2)
	{
		ListNode *h = h1;
		while (h2)
		{
			ListNode *t = h2;
			h2 = h2->next;
			t->next = h->next;
			h->next = t;
			h = t->next;
		}
	}
	void reverseList(ListNode *&pre)
	{
		ListNode *tail = pre->next;
		while (tail->next)
		{
			ListNode *t = tail->next;
			tail->next = t->next;//错误：tail = t->next
			t->next = pre->next;
			pre->next = t;
		}
	}
	int getLength(ListNode *h)
	{
		int len = 0;
		for ( ; h; h = h->next) len++;
		return len;
	}

目前的最佳答案：逻辑清晰，代码简练。

//2014-2-20 update
	void reorderList(ListNode *head)
	{
		if (!head || !head->next || !head->next->next) return;
		ListNode *pre = head->next;
		ListNode *tail = pre->next;

		while (tail && tail->next)
		{
			pre = pre->next;
			tail = tail->next->next;
		}
		reverseList(pre);

		tail = pre->next;
		pre->next = nullptr;
		intertwinedList(head, tail);
	}
	void intertwinedList(ListNode *&h1, ListNode *h2)
	{
		ListNode *h = h1;
		while (h2)
		{
			ListNode *t = h2;
			h2 = h2->next;
			t->next = h->next;
			h->next = t;
			h = t->next;
		}
	}
	void reverseList(ListNode *&pre)
	{
		ListNode *tail = pre->next;
		while (tail->next)
		{
			ListNode *t = tail->next;
			tail->next = t->next;//错误：tail = t->next
			t->next = pre->next;
			pre->next = t;
		}
	}