環(huán)境和原理是這樣的：
對于一個單向鏈表，只能順序訪問。對于這個鏈表的任意元素 itr。把itr 和itr->next的指向關系對調(diào)，變成一個新的鏈表，每次都把上一次反轉(zhuǎn)的第二個元素作為新鏈表的頭部，讓下次使用的第一個元素指向這個頭部。

為了把問題理解清楚，我把逆轉(zhuǎn)兩個元素的動作抽出來作為一個單獨的函數(shù)，
假設被反轉(zhuǎn)的節(jié)點為p1, p2為p1->next. 被反轉(zhuǎn)后的鏈表叫為tail,初始化tail =nullptr, 然后將tail作為新表的尾巴。
輸入?yún)?shù)為（tail，&p1，&(p1->next)），返回p2作為下次調(diào)用的結(jié)尾。

為了節(jié)約內(nèi)存，邏輯確實很復雜。

好了，你可以用代碼來試一下：

struct Node{
    struct Node *next;
//    struct Node *last;
    int data;
};


static Node *header;

void initList()
{
    header = new Node;
    Node *p = header;
    p->data = 0;
    
    for(int i = 1; i < 6; i++){
        p->next = new Node;
        p = p->next;
        p->data = i;
    }
    p->next = nil;
}
/*
void pointBackList()
{
    auto itr = header;
    itr->last = nil;
    
    for( ; itr->next != nil; itr = itr->next){
        itr->next->last = itr;
    }
    header = itr;
}
*/
Node* reverse_getNext(Node *lastHeader, Node **_p1, Node **_p2)
{
    Node *tmp = *_p2; //保存p2的地址
    (*_p2)->next = (*_p1);  //更新指針
    (*_p1)->next = lastHeader;
    return tmp;//返回舊的
}

Node * reverseList(Node* header)
{
    Node *tail = nullptr;
    Node *newHeader = header->next->next;
    tail = reverse_getNext(tail , &header, &(header->next));  //首次，頭為空.扭轉(zhuǎn)前兩個節(jié)點，返回第2個節(jié)點
    
    while(newHeader->next){
        Node *newHeaderTmp = newHeader->next->next;  //拿到第三個節(jié)點
        if(newHeaderTmp == nil){
            Node *lastNode = newHeader->next;
            lastNode->next = newHeader; //最后一個元素指向倒數(shù)第二個元素
            //更新后，倒數(shù)第二個元素指向反向列表的頭部
            newHeader->next= tail;
            tail = lastNode;
            break;
        }
        tail = reverse_getNext(tail , &newHeader, &(newHeader->next));  //扭兩個節(jié)點，返回第2個節(jié)點
        newHeader = newHeaderTmp;
    }
    
    return tail;
}

因為我用ios做的測試，所以Log自己改一下，測試用例大概是這樣子：

- (void)run
{
    initList();
    
    for(auto itr = header; itr != nil; itr = itr->next){
        NSLog(@"%d", itr->data);
    }
    
    header = reverseList(header);
    NSLog(@"\n");
    for(auto itr = header; itr != nil; itr = itr->next){
        NSLog(@"%d", itr->data);
    }
}

額外再說一點，留個last在Node里，是為了用另一種極端的辦法的，就是減少CPU消耗，使用很多內(nèi)存來反轉(zhuǎn)鏈表，實現(xiàn)把注釋去掉就行