面试题解读——反转链表

作者:冯老师,华清远见教育科技集团讲师。

题目: 写一道程序,完成将一个链表反转。

分析:很多人看到这个题目第一反应就是使用栈,因为栈的特性是先进后出后进先出。栈的方式的确可以完成,但是往往忽略一个问题——栈本身的构建也是需要大量代码的,作为面试题,面试官们肯定不会希望你使用栈的方式来实现它,因为我们有更好的方法来实现——头插法。

在链表的操作中,使用头插法本身就可以将一个数据按照相反的顺序插入,因此我们先将链表分为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;
        }