2 qq 33963483 qq_33963483 于 2016.03.17 14:17 提问

单链表的就地逆置 辅助空间为O(1)

求大神给个单链表的就地逆置 要不开拓辅助空间 原谅我没有C币

2个回答

cxsmarkchan
cxsmarkchan   2016.03.17 15:20
已采纳
struct Node{
    int value;
    Node *next;
};
void reverse(Node* head){
    Node *prev, *cur, *next;
    cur = head;
    prev = NULL;
    while(cur != NULL){
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
}
cxsmarkchan
cxsmarkchan 回复qq_33963483: 你可以自己画一个小的链表,然后模拟while循环中的每一步时,prev, cur, next都分别指向什么。模拟几步应该就能明白了。
接近 2 年之前 回复
cxsmarkchan
cxsmarkchan 回复qq_33963483: 这段代码的重点在于:你在改变cur的next指向时,一方面要知道cur的上一个对象是什么,所以需要prev来存;另一方面需要保存cur的下一个对象,不然改变了cur->next值之后,原来cur指向的元素就找不到了,所以要用一个next来暂存下一个对象。
接近 2 年之前 回复
qq_33963483
qq_33963483 可以帮我解释一下吗 还是有一点不懂
接近 2 年之前 回复
qq_33963483
qq_33963483   2016.03.17 18:55

可以帮我解释一下吗 还是有点不理解

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!