环境和原理是这样的:
对于一个单向链表,只能顺序访问。对于这个链表的任意元素 itr。把itr 和itr->next的指向关系对调,变成一个新的链表,每次都把上一次反转的第二个元素作为新链表的头部,让下次使用的第一个元素指向这个头部。

为了把问题理解清楚,我把逆转两个元素的动作抽出来作为一个单独的函数,
假设被反转的节点为p1, p2为p1->next. 被反转后的链表叫为tail,初始化tail =nullptr, 然后将tail作为新表的尾巴。
输入参数为(tail,&p1,&(p1->next)),返回p2作为下次调用的结尾。

为了节约内存,逻辑确实很复杂。

好了,你可以用代码来试一下:

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));  //首次,头为空.扭转前两个节点,返回第2个节点
    
    while(newHeader->next){
        Node *newHeaderTmp = newHeader->next->next;  //拿到第三个节点
        if(newHeaderTmp == nil){
            Node *lastNode = newHeader->next;
            lastNode->next = newHeader; //最后一个元素指向倒数第二个元素
            
//更新后,倒数第二个元素指向反向列表的头部
            newHeader->next= tail;
            tail = lastNode;
            break;
        }
        tail = reverse_getNext(tail , &newHeader, &(newHeader->next));  //扭两个节点,返回第2个节点
        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消耗,使用很多内存来反转链表,实现把注释去掉就行