单链表的逆置算法解析 |
您所在的位置:网站首页 › 单链表逆置输出的递归算法 › 单链表的逆置算法解析 |
问题描述:
比方说,一个不带头节点的单链表原来从头到尾存储的是(1, 2, 3, 4, 5),逆置后链表从头到尾存储的是(5,4,3,2,1) 解决思路:我暂时想到的有三种解法: 1)从头到尾依次访问旧的链表节点,每访问一个,就将这个节点的数据用头插的方法插入到新的链表中,这样当旧的链表访问完毕时,新的链表就构造成功了,然后释放掉原来的链表空间,将头指针指向新的链表头节点。 2)和第一个方法类似,也是从头到尾访问旧的链表节点,不同之处在于:每访问一个节点,就将这个节点插入到新的链表中,旧的链表访问完毕时,新的链表也构造成功了。这个因为没有申请新的节点空间,也没有释放旧的节点空间,所以 效率上要比第一个方法好很多。 3)采用就地逆置,即在旧的链表上直接逆置,操作完成后,旧的链表就被逆置成功了。这种方法既容易理解,效率又比较理想,我会重点讲这个方法。 第一种方法开始的时候定义两个指针,一个指向旧链表,一个指向新链表(开始的时候为空)。 然后申请一个节点并用旧链表的当前节点数值域填充新节点,将新节点采用头插法插入到新链表中,然后指向旧链表的指针向后走。 然后循环这个过程,直到遍历完旧链表。 第二种方法开始的时候状态和第一种相同 然后将旧链表的当前节点拆下来,头插法插入到新链表中。 重复这个过程,直到遍历完旧链表。 第三种方法最开始定义三个指针tmp, tmp_pre, tmp_next, 用tmp指向当前节点,tmp_pre指向当前节点的上一个节点,tmp_next指向当前节点的下一个节点。开始的时候tmp指向链表的第一个节点,其他两个指针指向NULL。 然后更新tmp(当前节点)的指针域,让其指针域指向上一个节点tmp_pre,但是如果直接更新,那么当前节点的下一个节点就找不到了,所以在更新当前节点的指针域之前,先保存下一个节点的地址,也就是让tmp_next指向tmp的下一个节点。 因为这个过程是循环进行的,所以要让指针沿着链表向后走。让tmp指向它的下一个节点,也就是刚才tmp_next指向的节点,因为tmp永远指向当前节点,tmp_pre永远指向当前节点的上一个节点,所以在让tmp向后走之前,先让tmp_pre指向tmp指向的节点。我画图把这个过程走一遍,结合图看这段话就能更容易理解。 1) 2) 3) 然后重复上面那个过程,直到走到链表的结尾,逆置成功。 实现代码第三种方法编码实现 void ListReverse(PNode* head){ assert(head); PNode ptr_pre = NULL; PNode ptr = *head; PNode ptr_next = NULL; while (ptr){ ptr_next = ptr->_link; //保存当前节点的下一个节点 ptr->_link = ptr_pre;//更新当前节点的指针域 ptr_pre = ptr;//更新当前节点上一个节点的位置 ptr = ptr_next;//更新当前节点的位置 } *head = ptr_pre;//更新头指针指向新链表第一个节点 } |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |