作者:冯老师,华清远见教育科技集团讲师。
题目: 写一道程序,完成将一个链表反转。
分析:很多人看到这个题目第一反应就是使用栈,因为栈的特性是先进后出后进先出。栈的方式的确可以完成,但是往往忽略一个问题——栈本身的构建也是需要大量代码的,作为面试题,面试官们肯定不会希望你使用栈的方式来实现它,因为我们有更好的方法来实现——头插法。
在链表的操作中,使用头插法本身就可以将一个数据按照相反的顺序插入,因此我们先将链表分为AB两部分,将原链表的头节点拆出作为A部分,后面的全部节点作为B部分,接下来一次从B部分中摘选一个节点按照头插法插入到A节点直到所有节点都从B移动到A部分为止。
以下是代码实现:
intlist_reverse(linklist_t *list)
{
Linknode_t *A = list; /* 原链表的头节点作为A部分 */
linknode_t *B = list->next; /*原链表除头节点意外的节点作为B部分*/
linknode_t *tmp = NULL; /* 临时指针,辅助标记节点位置 */
A->next = NULL; /* 先将A部分初始化,即将头节点的next置空 */
while (NULL != B) {
tmp = B; /* tmp标记B部分第一个节点的位置 */
B = B->next; /* B指针指向下一个节点,为下一次循环做准备 */
tmp->next = A->next; /*以下两部是普通的头插法,将tmp插入到A中 */
A->next = tmp;
}
return 0;
}