5 链表反转【有头结点】

此文是在前一文的基础上改进，两者区别在于是否有头结点，为何必须有头结点，笔者在《表》那一章已经说明了，此文是在上一节进行了改进。

【题目描述】

题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。

typedef int data_t;

typedef struct linklist_node_t
{
    data_t data;
    struct linklist_node_t *next;
}linklist_t;

【分析与解法】

这是一道广为流传的微软面试题。由于这道题能够很好的反应出程序员思维是否严密，在微软之后已经有很多公司在面试时采用了这道题。

为了正确地反转一个链表，需要调整指针的指向。与指针操作相关代码总是容易出错的，因此最好在动手写程序之前作全面的分析。在面试的时候不急于动手而是一开始做仔细的分析和设计，将会给面试官留下很好的印象，因为在实际的软件开发中，设计的时间总是比写代码的时间长。与其很快地写出一段漏洞百出的代码，远不如用较多的时间写出一段健壮的代码。

下面我们用图进行描述。

假设当前创建好的链表如下：

首先让头节点与第一个元素节点断开，但是要注意在断开之前需要用p指针指向第一个元素节点来保存第一个元素节点的位置，然后再断开。在这里有一个指针q指向一个指针域为空的节点，这个节点用来做为链表反转后的最后一个节点。

让第二个元素节点的指针从指向第三个元素节点变为指向第一个元素节点，以此类推，直至指针p指向原链表最后一个元素。

p指针指向NULL时，让原头节点的指针域指向原来最后一个元素节点。此时链表倒置已完成。

具体代码如下所示：

方法一：逐链反转

使用3个指针遍历单链表，逐个链接点进行反转。

linklist_t *linklist_reverse(linklist_t *head)
{
    linklist_t *p,*q,*pr;

    if(head == NULL)
    {
        return NULL;
    }

    p = head->next;//保存第一个元素节点的位置
    q = NULL;

    head->next = NULL;

    while(p)
    {
        pr = p->next;
        p->next = q;
        q = p;
        p = pr;
   }

    head->next = q;
    return head;
}

方法二：插入反转

对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。

依次插入即可。

代码如下所示：

linklist_t *linklist_reverse(linklist_t *head)
{
    linklist_t *p,*q;

    if(head == NULL)
    {
        return NULL;
    }
    p = head->next;
    while(p->next != NULL)
    {
        q = p->next;
        p->next = q->next;
        q->next = head->next;
        head->next = q;
    }
    return head;
}

【练一练】

【1、链表翻转】

给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。

【分析与解法】

这个就比较简单，可以参看上文的方法一，只是不反转整个链表，而是反转一部分，再将未反转的连接即可。

linklist_t *linklist_k_reverse(linklist_t *head,int k)
{
    int i;
    linklist_t *p,*q,*pr;

    if(head == NULL)
    {
        return NULL;
    }
    p = head->next;//保存第一个元素节点的位置
    q = NULL;

    head->next = NULL;

    for(i=0;i<k;i++)
    {
        pr = p->next;
        p->next = q;
        q = p;
        p = pr;
    }

    head->next = q;

    linklist_t *temp = head;
    while(temp->next)
    {
        temp = temp->next;
    }
    temp->next = p;
    return head;
}

相对方法一，方法二的时间复杂度更低，翻转几个数，只需要循环k-1次，无疑，这个效率是最高的。

linklist_t *linklist_k_reverse(linklist_t *head,int k)
{

    linklist_t *p,*q;

    if(head == NULL)
    {
        return NULL;
    }
    p = head->next;
    int i;
    for(i=0; i<k-1; i++)
    {
        q = p->next;
        p->next = q->next;
        q->next = head->next;
        head->next = q;
    }

    return head;
}

【2、逆序输出链表】

输入一个链表的头结点，从尾到头反过来输出每个结点的值。

【分析与解法】

这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。第一反应是从头到尾输出比较简单。于是很自然地想到把链表中链接结点的指针反转过来，改变链表的方向。然后就可以从头到尾输出了。

接下来的想法是从头到尾遍历链表，每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。该方法需要维护一个额外的栈，实现起来比较麻烦。

既然想到了栈来实现这个函数，而递归本质上就是一个栈结构。于是很自然的又想到了用递归来实现。要实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。

void PrintListReversely(linklist_t* pListHead)
{
    if(pListHead != NULL)
    {
        // Print the next node first
        if (pListHead->next != NULL)
        {
            PrintListReversely(pListHead->next);
        }

        // Print this node
        printf("%d ", pListHead->data);
    }
}

资源获取方法

1.关注公众号[嵌入式实验楼]
2.在公众号回复关键词[Data Structures and Algorithms]获取资料提取码