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

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

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

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

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)前兩個(gè)節(jié)點(diǎn)，返回第2個(gè)節(jié)點(diǎn)
    
    while(newHeader->next){
        Node *newHeaderTmp = newHeader->next->next;  //拿到第三個(gè)節(jié)點(diǎn)
        if(newHeaderTmp == nil){
            Node *lastNode = newHeader->next;
            lastNode->next = newHeader; //最后一個(gè)元素指向倒數(shù)第二個(gè)元素
            //更新后，倒數(shù)第二個(gè)元素指向反向列表的頭部
            newHeader->next= tail;
            tail = lastNode;
            break;
        }
        tail = reverse_getNext(tail , &newHeader, &(newHeader->next));  //扭兩個(gè)節(jié)點(diǎn)，返回第2個(gè)節(jié)點(diǎn)
        newHeader = newHeaderTmp;
    }
    
    return tail;
}

因?yàn)槲矣胕os做的測(cè)試，所以Log自己改一下，測(cè)試用例大概是這樣子：

- (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);
    }
}

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