重排序一个链表
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 node's values.
Example:Given 1->2->3->4->null , reorder it to 1->4->2->3->null
思路：将链表一分为二，逆序后半段，然后融合这两段链表。
ListNode *reorderList(ListNode *head)
{if(head == NULL || head->next == NULL || head->next->next == NULL)return head;//寻找到链表的中点ListNode *middle = findMiddle(head);//逆序后半部ListNode *right = reverse(middle->next);//middle成了前半部的终点,使其指向NULLmiddle->next = NULL;//融合头节点和后半部return merge(head,right);
}//寻找链表的中点
ListNode *findMiddle(ListNode *head)
{if(head == NULL || head->next == NULL)return head;ListNode *fastNode = head;ListNode *slowNode = head;//例如:1->2->3->4->5->6,//注意:如果链表长度为奇数个,中点很好找，分成的两段前一段比后一段多一个.//如果链表的长度为偶数个,如果下面的循环加上fastNode->next->next != NULL，那么//链表的两段元素个数相同,分别是1->2->3和4->5->6//如果不加fastNode->next->next != NULL，那么前一段的元素个数比后一段的元素个数多2个。//前段是1->2->3->4,后段是5->6->null，但是这并不影响最后的结果.//不加fastNode->next->next != NULL时，结果是1->6->2->5->3->4//加fastNode->next->next != NULL时,结果是1->6->2->5->3->4.//所以下面循环中的fastNode->next->next != NULL可不加.while(fastNode != NULL && fastNode->next != NULL && fastNode->next->next != NULL){fastNode = fastNode->next->next;slowNode = slowNode->next;}return slowNode;
}ListNode *reverse(ListNode *head)
{if(head == NULL || head->next == NULL) return head;ListNode *newHead = reverse(head->next);head->next->next = head;head->next = NULL;return newHead;
}ListNode *merge(ListNode *L1,ListNode *L2)
{if(L1 == NULL) return L2;if(L2 == NULL) return L1;ListNode *head = L1;ListNode *left = L1;ListNode *right = L2;while(L1 && L2){ L1 = L1->next;left->next = right;left = L1; L2 = L2->next;right->next = left;right = L2;}//left一定是大于等于right的.//相等的话L1和L2都是NULL//L1大于L2的话,L1不是NULL,是最后一个元素//这是针对本应用场景的mergeif(L1) L1->next = NULL;return head;
}/*另一个版本的merge，本版本是通用的合并两链表的算法,本版本优于上一种解法.*/void merge(ListNode *left,ListNode *right)
{if(left == NULL) return right;if(right == NULL) return left;ListNode *dummy = new ListNode(0);ListNode *tmp = dummy;while(left && right){dummy->next = left;dummy = dummy->next;left = left->next;dummy->next = right;dummy = dummy->next;right = right->next;}dummy->next = (NULL != left) ? left : right;delete tmp;
}