常用于面试的链表操作算法

比较有趣的链表操作
服务器君一共花费了214.842 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

链表操作在面试中会经常出现,下面列举的链表操作方法是比较典型的。

问题1:输入一个单向链表,输出该链表中倒数第k个结点

一个单向链表无法像数组一样可以直接索引,那么要找到链表的倒数第K个节点该怎么操作呢,其实思路非常简单,我们只需要设置两个指针p1,p2,首先p1和p2都指向链表的头部head,然后p2向前走k步,这样p1和p2之间就间隔k个节点,最后p1和p2同时向前移动,直至p2走到链表末尾,然后返回p1就是我们要找的链表的倒数K个节点。

struct ListNode{
    char data;
    ListNode *next;
};
ListNode *head, *p1, *p2;
ListNode *func(ListNode *head, int k){
    assert(k>=0);   //保证k应该要大于0
    p1 = p2 = head;
    for (; k>0; k--)
        p2 = p2->next;  //移动p2到与p1距离k个位置
    if (k>0)
        return   //要考虑到链表的元素可以小于k个
    while(p2!=NULL){
        p2 = p2->next;
        p1 = p1->next;     //移动p1,p2直到p2到达最后
}
return p1;
}

问题2:如何判断一个链表有环

这个问题可以这么来分析我们可以设置两个指针(p1, p2),初始值都指向头,p1每次前进一步,p2每次前进二步,如果链表存在环,则p2先进入环,p1后进入环,两个指针在环中走动,必定相遇,如何两节点相遇说明了这个链表存在一个环,以此思路给出了一下代码片段:

struct Node{
    int data;
    Node *next;
}
bool isCircle(Node *head, Node *CircleNode, Node *lastNode){
    Node *fast = head->next;  //步长为2的节点
    Node *slow = head;   //步长为1的节点
    while(fast != slow && fast && slow){  //当两节点不相遇且还未到达末尾时进行循环
        if (fast->next != NULL)
            fast = fast->next;
        if (fast->next ==NULL)
            lastNode = fast;    //记录尾节点
        if (slow->next = NULL)
            lastNode = slow;  //记录尾节点
        fast = fast->next;
        slow= slow->next;
}
if (fast == slow && fast && slow){
    CircleNode = fast;   //记录相遇的节点
    return True;
}
else
    return false;
}

问题3:如何判断两个链表是否相交

分析:问题可以分为两种情况,第一种情况如果两个链表都没有环的话,那么两个链表要是相交,那么从他们相交的那一点开始到尾节点两个链表应该完全相同,这样我们就可以直接判断链表的尾节点是否相同来进行判断两链表是否相交来进行判断。第二种情况的话如果两个链表存在环的话,那么我们则应该判断一链表上俩指针相遇的那个节点,在不在另一条链表上,如果在,则相交,如果不在,则不相交。由此可给出下面的代码片段:

bool detect(Node *head1, Node *head2){
    Node *circleNode1;   //链表1的相交节点
    Node *circleNode2;   //链表2的相交节点
    Node *lastNode1;     //链表1的尾节点
    Node *lastNode2;     //链表2的尾节点
    bool isCircle1 = isCircle(head1, circleNode1, lastNode1);   //判断链表1是否存在环
    bool isCircle2 = isCircle(head2, circleNode2, lastNode2);  //判断链表2是否存在环
    if (isCircle1 != isCircle2)
        return false;
    else if (!isCircle1 && !isCircle2){  //如果两链表都不存在环可以直接对尾节点进行比较看是否相交
        return lastNode1 == lastNode2;
}
else{              //如果连链表都存在环的话要看相交节点是不是在两链表都出现
    Node *temp = circleNode1->next;
    while(temp != circleNode1){
        if (temp == circleNode2)
            return true;
        temp = temp->next;
}
return false;
}
return false;
}

大概就这样,希望对你面试有用。

本文地址:http://www.nowamagic.net/librarys/veda/detail/780,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/780

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《链接器和加载器》 莱文(John R.Levine) (作者), 李勇 (译者)

《链接器和加载器》讲述构建程序的关键工具——链接器和加载器,内容包括链接和加载、体系结构、目标文件、存储分配、符号管理、库、重定位、加载和覆盖、共享库、动态链接和加载、动态链接的共享库,以及着眼于成熟的现代链接器所做的一些变化;并介绍一个持续的实践项目,即使用Perl语言开发一个可用的小链接器。《链接器和加载器》适合高校计算机相关专业的学生、实习程序员、语言设计者和开发人员阅读参考。

更多计算机宝库...