ReOrder List
2015 ワード
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}.
:(1) A,B 。
(2) 。
(3) A B 。//
#include<iostream>
#include<random>
using namespace std;
//
struct ListNode
{
int val;
ListNode *next;
};
//
void appendTail(ListNode **pHead, int val)
{
ListNode *pNew = new ListNode;
pNew->next = NULL;
pNew->val = val;
if (*pHead == NULL)
{
*pHead = pNew;
}
else
{
ListNode *tmp = *pHead;
while (tmp->next)
{
tmp = tmp->next;
}
tmp->next = pNew;
}
}
//
void show(ListNode *pHead)
{
while (pHead)
{
cout << pHead->val << " ";
pHead = pHead->next;
}
cout << endl;
}
//
void reverseList(ListNode *&head)
{
if (head == NULL || head->next == NULL)
return;
ListNode *p = head->next;
head->next = NULL;
while (p)
{
ListNode *tmp = p;
p = p->next;
tmp->next = head;
head = tmp;
}
}
//
void union_list(ListNode *pHead1, ListNode *pHead2)
{
ListNode *p = pHead1;
ListNode *q = pHead2;
while (q)
{
ListNode *tmp = q;
q = q->next;
tmp->next = p->next;
p->next = tmp;
p = tmp->next;
}
}
//
void reorderList(ListNode *head)
{
int num = 0;
ListNode *p = head;
while (p != NULL)
{
num++;
p = p->next;
}
ListNode *q = head;
for (int i = 0; i < (num + 1) / 2; ++i)
{
if (i == ((num+1)/2 - 1))
{
ListNode *tmp = q;
q = q->next;
tmp->next = NULL;
}
else
{
q = q->next;
}
}
reverseList(q);
union_list(head, q);
}
int main()
{
ListNode *pHead = NULL;
for (int i = 1; i < 1; ++i)
{
appendTail(&pHead, i);
}
reorderList(pHead);
show(pHead);
system("pause");
return 0;
}