• 欢迎访问BruceOu的博客,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本章吧

《数据结构与算法》第5章 链表反转【无头结点】(C语言)

数据结构与算法 BruceOu 5个月前 (07-04) 148次浏览 0个评论

24QYG9.md.png

5 链表反转【无头结点】

【题目描述】

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

typedef int data_t;

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

【分析与解法】

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

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

下面我们用图进行描述。

使用p和q两个指针配合工作,使得两个节点间的指向反向,同时用r记录剩下的链表。

“`
p = head;
q = head->next;
“`

RfdKnx.png

head->next = NULL;

Rfd1AO.png

现在进入循环体,这是第一次循环。

r = q->next;
q->next = p;

RfdBE8.png

p = q;
q =r;

Rfd4ET.png

接下来就是依次进行循环。最后将原头节点的指针域指向原来最后一个元素节点。具体代码如下所示:

【方法一:逐链反转】

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

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

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

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

    head->next = NULL;//旧的头指针是新的尾指针,next需要指向NULL

    while(q)
    {
        r = q->next;
        q->next = p;
        p = q;
        q = r;
   }
   head = p;//原头节点的指针域指向原来最后一个元素节点
   return head;
}

【方法二:插入反转】

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

RfwpPe.png

代码如下所示:

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;
    }
    p->next=head;//相当于成环
    head=p->next->next;//新head变为原head的next
    p->next->next=NULL;//断掉环

    return head;
}

【方法三:递归】

因为发现大部分问题都可以从递归角度想想,所以这道题目也从递归角度想了想。

递归的方法其实是非常巧的,它利用递归走到链表的末端,然后再更新每一个node的next 值 ,实现链表的反转。而newhead 的值没有发生改变,为该链表的最后一个结点,所以,反转后,我们可以得到新链表的head。

现在需要把A->B->C->D进行反转,

可以先假设B->C->D已经反转好,已经成为了D->C->B,那么接下来要做的事情就是将D->C->B看成一个整体,让这个整体的next指向A,所以问题转化了反转B->C->D。那么,可以先假设C->D已经反转好,已经成为了D->C,那么接下来要做的事情就是将D->C看成一个整体,让这个整体的next指向B,所以问题转化了反转C->D。那么,

可以先假设D(其实是D->NULL)已经反转好,已经成为了D(其实是head->D),那么接下来要做的事情就是将D(其实是head->D)看成一个整体,让这个整体的next指向C,所以问题转化了反转D。

接下来就用图来表示反转步骤。

Rfwkrt.png

程序刚开始执行,if 语句失效,进入 else 语句,然后执行

Node *newhead = linklist_reverse(head->next);

第二个结点的指针参数传入递归函数,一直到,最后一个结点的指针参数传入递归函数,if 语句有效:

head-> next == NULL;

返回当前的head 给 newhead 指针指向,如图:

RfwnPg.png

其实在递归函数栈内,按照后进先出的顺序,执行一级级的递归函数,返回末位结点给 newhead 之后,执行递归栈里的第二个递归函数,发生如图

RfwK2j.png

返回 newhead,也就是新的反转之后的链表(临时的),然后进入到递归工作栈里的第一个递归函数,如图:

Rfw1rq.png

返回 newhead,也就是反转之后的链表,此时递归工作栈的函数全部执行,返回的结点就是反转之后的链表的头结点(之前的尾结点)。

代码如下所示:

linklist_t *linklist_reverse(linklist_t *head)
{
    //如果链表为空或者链表中只有一个元素
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    else
    {
        //先反转后面的链表,走到链表的末端结点
        linklist_t *newhead = linklist_reverse(head->next);
        //再将当前节点设置为后面节点的后续节点
        head->next->next = head;
        head->next = NULL;
        return newhead;
    }
}
举一反三

【练一练】

[链表翻转]

给出一个链表和一个数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,*r;

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

    head->next = NULL;//旧的头指针是新的尾指针,next需要指向NULL

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

    //翻转的部分
    head = p;//原头节点的指针域指向原来最后一个元素节点

    linklist_t *t = head;
    //翻转的部分连接未反转的部分
    while(t->next)
    {
        t = t->next;
    }
    t->next = q;

    return head;
}

资源获取方法

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

嵌入式实验楼


BrueceOu , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:《数据结构与算法》第5章 链表反转【无头结点】(C语言)
喜欢 (1)
[支付宝]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址