楽ボタンT 143 OJ 1:チェーンテーブルc++を並べ替える
12336 ワード
問題の説明:
単一チェーンテーブルL:L 0→L 1→…→Ln-1→Lnが与えられ、
これを並べ替えて、L 0→Ln→L 1→Ln-1→L 2→Ln-2→…
単純にノード内部の値を変えるのではなく、実際にノード交換を行う必要があります.
例1:
チェーンテーブル1->2->3->4が与えられ、1->4->2->3に再配列する.
例2:
所与のチェーンテーブル1->2->3->4->5は、1->5->2->4->3に再配列する.
説明を入力:
まずチェーンテーブルの長さlenを入力し、次にlenの整数を入力してスペースで区切ります.
出力の説明:
出力フォーマットの例
注意:numが二重数の場合の交換終了条件はif(r->next)
単一チェーンテーブルL:L 0→L 1→…→Ln-1→Lnが与えられ、
これを並べ替えて、L 0→Ln→L 1→Ln-1→L 2→Ln-2→…
単純にノード内部の値を変えるのではなく、実際にノード交換を行う必要があります.
例1:
チェーンテーブル1->2->3->4が与えられ、1->4->2->3に再配列する.
例2:
所与のチェーンテーブル1->2->3->4->5は、1->5->2->4->3に再配列する.
説明を入力:
まずチェーンテーブルの長さlenを入力し、次にlenの整数を入力してスペースで区切ります.
出力の説明:
出力フォーマットの例
#include
using namespace std;
struct ListNode{
int val;
struct ListNode *next;
ListNode() : val(0), next(NULL) {
}
ListNode(int x) : val(x), next(NULL) {
}
ListNode(int x, ListNode *next) : val(x), next(next) {
}
};
class Solution
{
public:
void reorderList(ListNode* head)
{
//
ListNode *p,*q,*q_pre,*r;
p=head;r=head;q=head;
if(!head)return;
while(p->next)
{
r=p->next;
while(q->next->next){
q=q->next;
}
if(r->next){
q_pre=q;
q=q->next;
q->next=p->next;
p->next=q;
q_pre->next=NULL;
p=r;
r=p->next;
}
else break;
}
}
};
ListNode *createByTail()
{
ListNode *head;
ListNode *p1,*p2;
int n=0,num;
int len;
cin>>len;
head=NULL;
while(n<len && cin>>num)
{
p1=new ListNode(num);
n=n+1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
}
return head;
}
void displayLink(ListNode *head)
{
ListNode *p;
p=head;
cout<<"head-->";
while(p!= NULL)
{
cout<<p->val<<"-->";
p=p->next;
}
cout<<"tail
";
}
int main()
{
ListNode* head = createByTail();
Solution().reorderList(head);
displayLink(head);
return 0;
}
注意:numが二重数の場合の交換終了条件はif(r->next)