LeetCode Reorder List

LeetCode Reorder List

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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}.


本题要求把单链表重新排序,规则是第一个节点接最后一个节点,第二个节点接倒数第二个节点,以此类推。要求in-place,不能借助额外的空间。

这个题我一开始想到的是递归解法,就是首先把L0和Ln接好,然后递归的在L1->...->L(n-1)重排序。但是这样的算法性能肯定很差,因为首先要找到尾节点就很麻烦,还要递归的找尾节点。

看了网上的题解,发现真是巧妙。把链表重排序之后的结果其实相当于先把链表从中点分成前后两段,然后把后半段链表逆序,最后合并两个链表,合并的时候交替从两个链表中取节点拼接起来。

举个例子,0->1->2->3->4,中点是2,分成两段之后就是0->1和2->3->4,然后把第二个链表逆序为4->3->2,最后交替拼接这两个链表,结果就是0->4->1->3->2。、

所以知道思路之后就好办了,找中点可以用快慢指针法,链表逆序用头插法,最后拼接也不是什么难事,不过整合起来代码稍微有点长。

完整代码如下:

class Solution {
public:
	void reorderList(ListNode* head) {
		if (head == NULL || head->next == NULL || head->next->next == NULL)return;
		// find mid node
		ListNode *slow = head, *fast = head, *pre = slow;
		while (slow->next != NULL&&fast != NULL&&fast->next != NULL) {
			pre = slow;
			slow = slow->next;
			fast = fast->next->next;
		}
		pre->next = NULL;
		// reverse [mid,end]
		ListNode *par = new ListNode(0), *tail;
		while (slow) {
			tail = slow->next;
			slow->next = par->next;
			par->next = slow;
			slow = tail;
		}
		//merge 2 list
		par = par->next;
		ListNode *new_head = new ListNode(0), *h = new_head;
		while (head || par) {
			if (head == NULL) {
				h->next = par;
				par = par->next;
			}
			else {
				h->next = head;
				head = head->next;
				h = h->next;
				h->next = par;
				par = par->next;
			}
			h = h->next;
		}
		head = new_head->next;
	}
};

本代码提交AC,用时59MS。

Leave a Reply

Your email address will not be published. Required fields are marked *