链表操作 算法面试题

时间:2021-04-16 09:42:49

1、给定单链表的头指针和一个结点指针,在O(1)时间删除该结点。

算法描述:删除单链表的一个节点需要知道该节点的前驱和后继。实际上找到前驱的平局时间复杂化度就是O(1).
传送阵:http://blog.csdn.net/wcyoot/article/details/6426691

2、输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

算法描述:定义两个节点指针p1,p2,使p2-p1相距为k,然后同步后移,当p2为链表节点尾指针时,p1即为倒数第k个节点。
传送阵:http://blog.csdn.net/wcyoot/article/details/6428297

3、判断一个单向链表是否有环。

算法描述:初始定义两个指针p1,p2均指向链表头,使其中一个步长为1,另一个步长为2。在到达链表尾节点前出现p1==p2,即该单链表有环。

4、寻找单向链表的环入口,即进入环的第一个节点。

算法描述:1)判断该链表是否有环,即初始定义两个指针p1,p2均指向链表头,使其中一个步长为1,另一个步长为2。判断在到达链表尾节点前出现p1==p2,如果不存在,则无环,如果存在,设p=p1.
2)设q为链表头节点,将q与p同时以步长为1后移,当二者相同时,即为环入口。
算法分析与源码:http://blog.csdn.net/wcyoot/article/details/6426436

5、给定两个单向链表,找出它们的第一个公共结点。

问题分析:1)如果他们存在公共节点,那么第一个公共节点后的链接节点将是相同的;
2)需要判断两个单链表是否有环。
3)两个链表中没有环的算法:假设两个链表的长度分别为m,n,(m>=n),则将长链表的第m-n+1个节点与短链表的头节点对齐,依次比较后继节点,第一个相同的节点就是第一个公共节点。
算法描述:1)计算两个链表的环入口,如果无环则环入口为NULL;
2)如果两个链表的环入口均为NULL,则两个链表均没有环,按两个链表均没有环的算法处理;
3)如果两个链表的环入口只有一个为NULL,则两个链表无公共交点;
4)如果两个链表的环入口均不为NULL,且相同,则将环入口作为两个链表的尾节点,按没有换的两个链表求第一公共节点处理
5)如果两个链表的环入口均不为NULL,且不同,则需要判断一个链表的环入口是否在另一个链表的环上,如果不在,没有公共节点,如果在,则可认为任一环入口为第一公共节点
算法具体分析与源码:http://blog.csdn.net/wcyoot/article/details/6426436

6、复杂链表的复制

有一个复杂链表,其结点除了有一个m_pNext指针指向下一个结点外,还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下:
struct ComplexNode
{
    int m_nValue;
    ComplexNode* m_pNext;
    ComplexNode* m_pSibling;
};                              
请完成函数ComplexNode* Clone(ComplexNode* pHead),以复制一个复杂链表。

算法分析:首先设原链表为:a-b-c-d-e,接着插入新链表a-a'-b-b'-c-c'-d-d'-e-e',新节点中的m_pSibling全设为NULL。第一遍完成以后,第二遍遍历链表,更新a',b',c',d',e'的m_pSibling域(更新方法,以a'为例,a'->m_pSibling=a'的前一个节点的m_pSibling->next)。第三遍把链表拆成两个部分。算法复杂度o(N)

7、将一个二元查找树转换为一个排序的双向链表

问题描述:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。
算法分析:中序遍历二元查找数的结果就是有序的目标节点顺序。只需按中序遍历的顺序把节点链接到链表尾端即可。
传送阵:http://blog.csdn.net/wcyoot/article/details/6428297

8、合并两个有序的单向链表

问题分析:1)没有说明两个链表是否交叉,需要考虑这种情况
2)合并两个不交叉的有序单向链表的算法:设排序规则为G(x1, x2),同步遍历两个链表的游标指针p1,p2,插入游标p;如果满足G(p1,p2)则将p1插入p后,p和p1后移;否则将p2插入p后,p和p2后移。如果p1,或p2有一个为NULL,则将另一个指针后的所有元素插入到p后。
算法描述:设排序规则为G(x1, x2),同步遍历两个链表的游标指针p1,p2,插入游标p;
1)初始化p1为链表1的头指针,p2为链表2的头指针,p=NULL;
2)如果p1==p2,则两个链表存在公共点,p1后的所有节点相同,将p1后的所有节点链在p后,结束。
3)如果p1或p2有一个为NULL,将非空的那个指针后的所有元素链在p后,结束
4)如果满足G(p1,p2)则将p1插入p后,p和p1后移,否则将p2插入p后,p和p2后移;继续步骤2)

9、单链表交换任意两个节点(不含表头)

算法描述:将两个节点存储的数据进行交换即可。不必真的交换节点。

10、用单链表模拟大整数加法运算

问题描述:例如:9>9>9>NULL + 1>NULL => 1>0>0>0>NULL
问题分析:设两个链表A,B,求链表C,满足C=A+B
算法一:将链表A和B反转,将A和B相加合并。将进位加到下一节点,如果一个比较长,直接合并;如果最后有一个进位,在链表尾创建新的节点。最后将合并后的链表再次反转。
算法二:求得链表A和B的长度,以递归的方式计算对应为相加,如果有进位,在链表头插入新建节点。

11、将二级单链表展开成一级单链表

问题描述:有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表展开成一级单链表。
/*这个二级单链表只包括一些head*/
public class Link
{    
    public Link Next;    
    public int Data;    
    public Link(Link next, int data)    
    {        
        this.Next = next;        
        this.Data = data;    
    }
}
public class CascadeLink
{
    public Link Next;  
    public CascadeLink NextHead; 
    public CascadeLink(CascadeLink nextHead, Link next) 
    {       
        this.Next = next;    
        this.NextHead = nextHead;  
    }
}

算法描述:遍历,使A.Next的尾节点.Next = A.NextHead.Next.

12、单链表排序

算法分析:单链表元素交换有两种:一、直接交换值;二、交换节点。并且单链表执行插入操作时不会引起数据移动。
传送阵:参考http://blog.csdn.net/wcyoot/article/details/6427247

13、删除单链表中重复的元素

算法描述:使用hashtable辅助,如果存在即删除,如果不存在将值写入hashtable。

14、删除两个双向循环链表中值相同的节点。

算法描述:1)<key,value>的map对象m,其中key为链表的值,value为链表节点指针;遍历双向循环链表A,构造键值对写入辅助对象m中
2)遍历B,如果当前节点cur的值在map中存在,删除cur节点并使cur后移,同时判断m[cur.value]的值是否为NULL,如果不为空删除其对应在A中的节点,并使m[cur.value]=NULL