程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode] Reorder List

[LeetCode] Reorder List

編輯:C++入門知識

[LeetCode] Reorder List


 

Reorder List

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}.

解題思路:

這道題比較簡單,弄清楚題意,然後鏈表操作即可。大體思路是,先計算鏈表長度,然後將鏈表一分為二。後半部分鏈表翻轉,然後將兩個鏈表合並。注意一些邊界條件,比如,若鏈表長度為奇數,前一個鏈表多分一個;若為偶數,兩個鏈表一樣多。為簡便起見,分別分配兩個新表頭。代碼如下:

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==NULL){
            return;
        }
        int len = getListLength(head);
        ListNode* head1 = new ListNode(0);
        ListNode* head2= new ListNode(0); //head2表示後半部分倒轉
        head1->next = head;
        ListNode* p = head1;
        for(int i=(len+1)/2; i>0; i--){
            p=p->next;
        }
        //此時p表示head1前一個節點
        ListNode* q=p->next;
        p->next=NULL;
        //將後半部分翻轉到head2中
        while(q!=NULL){
            p=q->next;
            q->next=head2->next;
            head2->next=q;
            q=p;
        }
        //將兩個鏈表合並
        p=head1->next;
        while(head2->next!=NULL){
            q=head2->next;
            head2->next = q->next;
            q->next=p->next;
            p->next=q;
            p=q->next;
        }
        head=head1->next;
        delete head1;
        delete head2;
    }
    
    int getListLength(ListNode* head){
        int len = 0;
        while(head!=NULL){
            len++;
            head=head->next;
        }
        return len;
    }
};


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved