HackerRank上的单链表问题总结

这两天比较闲,因此刷了几道HackerRank上的题目。下面简单将其中与单链表操作有关的题目集中总结一下。


首先给出这些题目中通用的单链表节点定义:

第一题:顺序打印单链表中的元素。
思路:从头节点处开始遍历输出,直至NULL。
代码:

第二题:给定一个数值,生成一个新数值并插入到单链表的尾部。
思路:遍历到尾节点,然后创建一个新的节点,让尾节点的next指针指向这个新的节点。
代码:

第三题:给定一个数值,生成一个新节点插入到单链表的头部。
思路:创建一个新的节点,让这个新节点的next指针指向原来链表的头部。
代码:

第四题:给定一个位置和数据,生成一个新节点并插入到单链表的相应位置处。
思路:保持一个计数器,然后开始遍历单链表,同时计数器进行更新,当计数器的值与位置相等时,表示找到了要插入的位置了,之后的做法类似于第三题。
代码:

第五题:从单链表中删除一个给定位置处的节点。
思路:很简单,不多说了。
代码:

第六题:逆序打印单链表中的元素。
思路:使用递归。
代码:

第七题:将一个单链表中的所有元素逆序。
思路:首先需要确定这个单链表是带有头节点的还是不带有头节点的,带有头节点的链表在处理起来稍微复杂一点。然后可以用三个指针,分别指向当前节点cur,前一个节点pre,后一个节点next,然后调整这三个节点之间的指向关系。
代码:

第八题:比较两个单链表中的元素是否相同
思路:用两个指针分别遍历两个链表,然后比较指针指向的节点数值是否相等。
代码:

第九题:合并两个有序单链表,将合并的结果放在一个新链表中。
思路:用两个指针来分别遍历两个链表,比较这两个指针指向的节点的数值大小,
若A<B,那么A++,拷贝A的数据到C,直到A>B;若A>B,则B++,拷贝B的数据到C,直到B>A;若A==B,则A++,B++,拷贝A或B到C。若其中一条链表先遍历完,则将另一条链表的数据直接拷贝到C中。
代码:

第十题:获得离一个链表尾部距离为K的节点。
思路:设置两个指针,初始化时均指向头节点,然后让一个指针先往前移动K个节点,然后这两个指针再一起向前移动,当第一个指针指向链表的尾部时,第二个节点所指的位置正好就是离尾部距离为K的节点。
代码:

第十一题:删除一个有序单链表中的重复元素。
思路:用两个指针分别指向当前节点cur和下一节点fol,当fol和cur的数值相等时,fol++,直到不再相等,调整cur和fol,然后cur++。
代码:

第十二题:检测链表中是否有环。
思路:使用两个指针,一个指针每次往前移动一个节点,一个指针每次往前移动两个节点,若是链表中有环的话,那么这两个指针一定会相遇,因此可以用这两个指针是否会相等来检测链表中有没有环。
代码:

第十三题:找到两个链表的合并点。
思路:首先计算出这两个链表的长度和长度差,然后设置两个指针分别指向这两个链表的头部,让长的那个指针先移动长度差个节点,然后两个指针再一起向前移动,当这两个指针相等的时候,所指的点就是这两个链表的合并点。
代码:

第十四题:向一个有序双向链表中插入一个节点。
思路:和向单链表中插入节点思路相同,只不过节点的前后关系设置多了几步。
代码:

第十五题:逆序一个双向链表。
思路:和逆序一个单链表思路一致,并且由于节点中本身就有prev和next信息,因此只需要用一个指针指向当前节点即可。
代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注