首页 > 代码库 > leetcode:Reorder List

leetcode:Reorder List

问题

Given a singly linked list LL0L1→…→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}.

代码
class Solution {
public:
    void reorderList(ListNode *head) {
		if(head==NULL||head->next==NULL)
			return ;
		/*[快速求出链表的中间结点]通过两个结点,一个走1个步长,一个走2个步长,最后算出链表的中间结点middleNode*/ 
		ListNode *midNode=head;
		ListNode *stepNode=head;
		while(stepNode!=NULL&&stepNode->next!=NULL&&stepNode->next->next!=NULL)
		{
			midNode=midNode->next;
			stepNode=stepNode->next->next;
		}
         /*分成两个链表,将链表中间结点之后的链表(链表的后半部分)逆序*/
                ListNode *head1=head;
		ListNode *head2=midNode->next;
		midNode->next=NULL;
		ListNode *p=head2->next;//开始求逆序
		head2->next=NULL;
		while(head2&&p)
		{
			ListNode *tmp=p->next;
			p->next=head2;
			head2=p;
			p=tmp;
		}
		/*完成链表前半部分和逆序后的后半部分的结合!*/
		
		while(head1!=NULL&&head2!=NULL)
		{
			ListNode *tmp1=head1->next;
			ListNode *tmp2=head2->next;
			head1->next=head2;
			head2->next=tmp1;
			head1=tmp1;
			head2=tmp2;
		}
    }
};

复杂度

时间复杂度:O(N)。