Linked List

一、链表

链表是面试中十分容易考到的题目,一般代码比较短,而且考查面试者的思维全面性和写无bug代码的能力。在写链表的题目时,建议画出示意图,并把头结点、尾节点这些特殊的结点考虑在内。

常考题型如下:

题一、 给定单链表,检测是否有环

题二、 给定两个单链表(head1, head2),检测两个链表是否有交点,如果有返回第一个交点。

题三、 给定单链表(head),如果有环的话请返回从头结点进入环的第一个节点。

题四、只给定单链表中某个结点p(并非最后一个结点,即p->next!=NULL)指针,删除该结点。

题五、只给定单链表中某个结点p(非空结点),在p前面插入一个结点。

题六、给定单链表头结点,删除链表中倒数第k个结点

题七、复杂链表复制

题八、两个不交叉的有序链表的合并

题九、链表翻转(包括全翻转,部分翻转,分段翻转)(递归或非递归实现)

题十、实现链表排序的一种算法

题十一、删除有序单链表中重复的元素

题十二、用链表模拟大整数加法运算

链表可以说是面试高频必问知识点,而关于链表的题目也比较固定。以上题目在剑指offer上大多出现过。本部分主要整理了几个比较典型常考的题目。

二、目录