チェーンテーブルReorder Listを並べ替える
2369 ワード
leetcodeのタイトルは次のように記述されています.
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つの部分に分けます;2後の部分を逆転する.3 2つの部分を結合します.コードは次のとおりです.
#include #include using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution{public:void reorderList(ListNode*head){ListNode*tmp_resultListNode=new ListNode(0);//一時的な結果チェーンテーブルが後を絶たないListNode*resultListNode=tmp_resultListNode;//だから最終結果チェーンテーブルがこのアドレスbool flag=trueを指す必要がある;ListNode*right ListNode=findListMidNode(head);//後半のチェーンテーブルListNode*reserveRightListNode=reserveList(rightListNode);//後半チェーンテーブルの逆ListNode*leftListNode=headを求める;//このときのheadは前半のみです.findListMidNodeではwhile(leftListNode!=NULL‖reserveRightListNode!=NULL)//2つのチェーンテーブルが空でない限り、マージ{if(flag)//trueを行い、前の{tmp_resultListNode->next=leftListNode;leftListNode=leftListNode->next;}Else//がfalseの場合、後に{tmp_resultListNode->next=reserveRightListNode;reserveRightListNode=reserveRightListNode->next;tmp_resultListNode = tmp_resultListNode->next;//仮結果チェーンテーブルプッシュ後flag=!flag;}head = resultListNode->next;//最終結果をヘッダポインタ}ListNode*findListMidNode(ListNode*head)//チェーンテーブルの中間ポインタを探し、チェーンテーブルを2つの部分{if(head=NULL)return head;ListNode*p=head;ListNode*q=p->next;while(q!=NULL&&q->next!=NULL){p=p->next;q=q->next->next;q = p->next;p->next=NULL;return q;}ListNode*reserveList(ListNode*head)/チェーンテーブルに対して逆{if(head=NULL)return head;ListNode*p=head;ListNode*tmp_resultList=new ListNode(0);ListNode*resultList=tmp_resultList;vectortmp_val;//順序チェーンテーブルを保存して得られた結果while(p!=NULL){tmp_val.push_back(p->val);p=p->next;}for (int i =tmp_val.size()-1;i>=0;i-)/逆保存チェーンテーブル{tmp_resultList->next=new ListNode(tmp_val[i]);tmp_resultList=tmp_resultList->next;}return resultList->next;//結果を返す}};void main() {Solution s;ListNode *head1 = new ListNode(2);head1->next = new ListNode(4);head1->next->next = new ListNode(6);head1->next->next->next = new ListNode(3);head1->next->next->next->next = new ListNode(5);head1->next->next->next->next->next = new ListNode(1);s.reorderList(head1);while(1); }
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まずチェーンテーブルを対称の2つの部分に分けます;2後の部分を逆転する.3 2つの部分を結合します.コードは次のとおりです.
#include #include using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution{public:void reorderList(ListNode*head){ListNode*tmp_resultListNode=new ListNode(0);//一時的な結果チェーンテーブルが後を絶たないListNode*resultListNode=tmp_resultListNode;//だから最終結果チェーンテーブルがこのアドレスbool flag=trueを指す必要がある;ListNode*right ListNode=findListMidNode(head);//後半のチェーンテーブルListNode*reserveRightListNode=reserveList(rightListNode);//後半チェーンテーブルの逆ListNode*leftListNode=headを求める;//このときのheadは前半のみです.findListMidNodeではwhile(leftListNode!=NULL‖reserveRightListNode!=NULL)//2つのチェーンテーブルが空でない限り、マージ{if(flag)//trueを行い、前の{tmp_resultListNode->next=leftListNode;leftListNode=leftListNode->next;}Else//がfalseの場合、後に{tmp_resultListNode->next=reserveRightListNode;reserveRightListNode=reserveRightListNode->next;tmp_resultListNode = tmp_resultListNode->next;//仮結果チェーンテーブルプッシュ後flag=!flag;}head = resultListNode->next;//最終結果をヘッダポインタ}ListNode*findListMidNode(ListNode*head)//チェーンテーブルの中間ポインタを探し、チェーンテーブルを2つの部分{if(head=NULL)return head;ListNode*p=head;ListNode*q=p->next;while(q!=NULL&&q->next!=NULL){p=p->next;q=q->next->next;q = p->next;p->next=NULL;return q;}ListNode*reserveList(ListNode*head)/チェーンテーブルに対して逆{if(head=NULL)return head;ListNode*p=head;ListNode*tmp_resultList=new ListNode(0);ListNode*resultList=tmp_resultList;vectortmp_val;//順序チェーンテーブルを保存して得られた結果while(p!=NULL){tmp_val.push_back(p->val);p=p->next;}for (int i =tmp_val.size()-1;i>=0;i-)/逆保存チェーンテーブル{tmp_resultList->next=new ListNode(tmp_val[i]);tmp_resultList=tmp_resultList->next;}return resultList->next;//結果を返す}};void main() {Solution s;ListNode *head1 = new ListNode(2);head1->next = new ListNode(4);head1->next->next = new ListNode(6);head1->next->next->next = new ListNode(3);head1->next->next->next->next = new ListNode(5);head1->next->next->next->next->next = new ListNode(1);s.reorderList(head1);while(1); }