链表面试题
前言：
在面试中，最经常被提及的就是链表，，但又因为需要对指针进行操作，凡是涉及到指针的，都需要我们具有良好的编程基础才能确保代码没有任何错误。
链表是一种动态的数据结构，因为在创建链表时，我们不需要知道链表的长度，当插入一个结点时，只需要为该结点分配内存，然后调整指针的指向来确保新结点被连接到链表中。所以，它不像数组，内存是一次性分配完毕的，而是每添加一个结点分配一次内存。正是因为这点，所以它没有闲置的内存，比起数组，空间效率更高。
在这里我整理了一部分的链表面试题，希望对大家有所帮助。
1. 从尾到头打印单链表
方法一：可以把链表中链接节点的指针反转过来，改变链表的方向，然后就可以从头到尾输出了 。但是这种方法会改变链表本身的结构。是否改变链表的结构？这取决于题目的要求。
方法二：可以考虑用栈来实现。遍历链表的顺序是从头到尾，而输出的顺序是从尾到头，这就是典型的“后进先出”。每经过一个节点，就把该节点的数据存放到栈中，遍历结束后再从栈中取出来。而栈本质上就是递归，此处可以用递归来实现。
方法三：可以多遍历几遍，每次遍历到链表的末尾，打印；再从头遍历到末尾的前面一个节点，打印；如此反复。
void PrintTailToHead(pNode plist)
{
if (plist == NULL)
return;
if (plist->next == NULL)
printf("%d", plist->data);
pNode cur = plist;
pNode tail = NULL;
while (plist != tail)
{
cur = plist;
while (cur->next != tail)
{
cur = cur->next;
}
printf("%d-->", cur->data);
tail = cur;
}
printf("Over\n");
}
void PrintTailToHeadR(pNode pList)//递归实现
{
if(pList != NULL)
{
if(pList->next != NULL)
{
PrintTailToHeadR(pList->next);
}
printf("%d-->", pList->data);
}
}2. 删除一个无头单链表的非尾节点
这道题的意思是不给头节点，只给需要删除的这个非尾节点。很多人第一次接触这个题目有点束手无策，因为我们要删除一个单链表的某个节点，需要让这个节点的上一个节点指向这个节点的下一个节点，从而达到删除的目的。而此题不给头节点就会让人没有头绪，因为单向链表只能单向遍历，不能找到它前面的节点，而相交于找前面一个节点，我们可以找后面一个节点，因为本节点中就含有指向下一个节点的指针。我们可以把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除，那其实也就是相当于将当前的结点删除。
void EraseNotTail(pNode pos)//把后面一个节点的值赋给它本身，再删除它后面的那个节点
{
pNode del = NULL;
assert(pos != NULL);
assert(pos->next != NULL);
del = pos->next;
pos->data = pos->next->data;
pos->next = pos->next->next;
free(del);
del = NULL;
}3.在一个无头节点的插入一个节点
此题跟上一题有些相似，单向链表只能在某个无头节点的后面插入一个节点，再把这两个节点的数据交换。
void InsertNode(pNode pos, Datatype d)
{
pNode NewNode = BuyNode(d);
NewNode->next = pos->next;
pos->next = NewNode;
Datatype tmp = pos->data;
pos->data = NewNode->data;
NewNode->data = tmp;
}4.单链表实现约瑟夫环
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。单链表实现约瑟夫环首先需要一个环，只需要单链表的最后一个节点的next指向头结点即可形成一个环。然后从第一个结点开始报数，当数到3的时候的那个结点就被抛出，然后从下一个开始又重新从1开始继续报数，从而留下最后一个结点，就是约瑟夫点。
void pLinkNodeJosephCycle(pNode * pplist, int num)
{
pNode cur = NULL;
assert(pplist != NULL);
cur = *pplist;
while(cur->next != cur)
{
for (int i = 1; i < num; i++)
{
cur = cur->next;
}
pNode dell = cur->next;
cur->data = dell->data;
cur->next = dell->next;
free(dell);
dell = NULL;
}
printf("%d\n", cur->data);
//cur->next = NULL;
//DestroyLinkList(&cur);//DestroyLinkList函数要遇到空才会停下来，所以要cur->next=NULL
free(cur);
cur = NULL;//两种删除方法均可
}5.逆置/反转单链表
此处采用前插法
Node* ReverseList(pNode * pplist)
{
pNode cur = NULL;
pNode cur1 = NULL;
pNode cur2 = NULL;
assert(pplist != NULL);
assert(*pplist != NULL);
cur = *pplist;
while (cur)
{
cur1 = cur->next;
cur->next = cur2;
cur2 = cur;
cur = cur1;
}
return cur2;
}
6.单链表排序（冒泡排序）
链表中的冒泡排序跟数组中的冒泡排序差别不大，都是两层循环
void BubbleSort(pNode * pplist)
{
pNode cur = NULL;
pNode next = NULL;
pNode tail = NULL;
assert(pplist != NULL);
cur = *pplist;
while (cur != tail)
{
cur = *pplist;
next = cur->next;
while (next != tail)
{
if ((cur->data) > (next->data))
{
Datatype tmp = cur->data;
cur->data = next->data;
next->data = tmp;
}
cur = next;
next = cur->next;
}
tail = cur;//每次排完一趟序就吧tail指针往前移一个指针
}
}7.合并两个有序链表,合并后依然有序
此处我们假设两条链表都是升序。首先我们应该先创立一个新的链表NewList，它指向空。然后用两个指针p1、p2分别指向两条需要排序的链表的头节点，比较这两个节点值的大小，把数值较小的这个节点（假设是p1）链到NewList后面（尾插），再把p1往后移一下，再次比较p1、p2节点值的大小，知道某条链表到尾为止。接下来就可以直接把另外一条没有到尾的链表的后续直接链上NewList（尾插）。
Node* Merge(pNode list1, pNode list2)
{
pNode NewList = NULL;
pNode tail = NULL;
assert(list1 != NULL);
assert(list2 != NULL);
if ((list1->data) < (list2->data))
{
NewList = list1;
list1 = list1->next;
}
else
{
NewList = list2;
list2 = list2->next;
}
tail = NewList;
while ((list1 != NULL) && (list2 != NULL))
{
if ((list1->data) < (list2->data))
{
tail->next = list1;
list1 = list1->next;
}
else
{
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
if (list1 == NULL)
{
tail->next = list2;
}
if (list2 == NULL)
{
tail->next = list1;
}
return NewList;
}8.查找单链表的中间节点，要求只能遍历一次链表
此题我们可以使用两个指针同时遍历，一个指针每次往后走一步，另外一个指针每次走两步，走两步的这个指针会先到达链表的末尾，当走的快的这个指针到达链表的末尾时，走得慢的这个指针刚好指向链表的中间节点。
Node* FindMidNode(pNode plist)
{
Node *p1 = NULL;
Node *p2 = NULL;
assert(plist != NULL);
p1 = plist;
p2 = plist;
while (p1 != NULL&&p1->next != NULL )
{
for (int i = 0; i < 2; i++)
{
p1 = p1->next;
}
p2 = p2->next;
}
Node *p3 = p2;
p3->next = NULL;
return p3;
}9.查找单链表的倒数第k个节点，要求只能遍历一次链表
有了上面一题做铺垫，这个题是否有思路呢，创立两个指针，都指向链表头节点，先让其中一个节点往后面移k步，再让两个指针同时往后面移，当先移k步的指针指针指向最后一个节点，另外一个节点是不是就是倒数第k个指针呢？
void FindLastKNode(pNode *pplist, int k)
{
pNode p1 = NULL;
pNode p2 = NULL;
assert(pplist != NULL);
p1 = *pplist;
p2 = *pplist;
for (int i = 1; i < k; i++)
{
if(p1->next != NULL)
p1 = p1->next;
else
{
printf("链表不够长，没有倒数第%d个元素\n", k);
return;
}
}
while (p1->next != NULL)
{
p1 = p1->next;
p2 = p2->next;
}
printf("%d\n", p2->data);
}10.判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复杂度&空间复杂度。
此处有三个问题，问题一：单链表是否带环。如果带环，单链表是没有尾的（即没有一个next会指向NULL）；我们可以上面求中间指针的方法，让一个指针每次走两步，另外一个指针每次走一步，如果每次走两步的指针遇到了NULL就证明链表没有成环，否则链表则成环。
Node* CheckCycle(pNode pList)
{
pNode cur1 = NULL;
pNode cur2 = NULL;
assert(pList != NULL);
cur1 = pList;
cur2 = pList;
if ((cur1->next == NULL) || (cur1->next->next == NULL))
return NULL;
do
{
cur1 = cur1->next->next;//一个指针走两步，另外一个走一个，如果是环的话，两个指针终究会相遇
cur2 = cur2->next;
} while ((cur1 != NULL) && (cur1->next != NULL) //不成环
&& (cur1 != cur2));//成环
if (cur1 == cur2)
{
return cur1;
}
else
{
return NULL;
}
}问题二：如果成环，求环的长度。在问题一中我们返回的是快慢指针相遇的节点，此时我们可以再创立两个节点都指向相遇的节点，同时创立一个count=1用于计数，让一个指针每次往后走两步，另外一个指针每次往后面走一步，没走一次count就+1。当两个指针相遇时，count的值就是环的长度。
int GetCircleLength(pNode meet)
{
pNode fast = meet;
pNode slow = meet;
int count = 0;
do
{
fast = fast->next->next;
slow = slow->next;
count++;
} while (fast!= slow);
return count;
}问题三：如果成环，求环的入口
如下图所示：
pNode GetCycleEntryNode(pNode list, pNode meetNode)
{
while (list != meetNode)
{
list = list->next;
meetNode = meetNode->next;
}
return list;
}11.判断两个链表是否相交，若相交，求交点。（假设链表不带环）
问题一：两个不带环链表相遇的话，两个链表的尾是一样的，抓住这一点就可以了。
问题二：如果相交，求交点。两个链表在交点之后都是一样的，不同的只是前面的部分，假设链表一比链表二长2个节点，创立两个指针p1，p2分别指向链表一的头节点和链表二的头节点，先让p1往后走两步，再让两个链表同时往后走，当两个节点一样时，这个节点就是两个链表的交点。
Node * CheckCross(pNode list1, pNode list2)
{
int len1 = 0;
int len2 = 0;
pNode cur1 = NULL;
pNode cur2 = NULL;
assert(list1&&list2);
cur1 = list1;
cur2 = list2;
while (cur1->next != NULL)
{
cur1 = cur1->next;
len1++;
}
while (cur2->next != NULL)
{
cur2 = cur2->next;
len2++;
}
if (cur1 == cur2)//走到尾，如果相同则相交
{
int diff = abs(len1 - len2);
if (len1 > len2)
{
cur1 = list1;
cur2 = list2;
}
else
{
cur1 = list2;
cur2 = list1;
}
for (int i = 0; i < diff; i++)
{
cur1 = cur1->next;
}
while (cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
else
{
return NULL;
}
}12.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】
问题一：先判断这两个链表是否带环：
①如果两个链表都不带环，可以直接采用上一个题目的方式判断；
②如果一个带环，一个不带环，则这两条链表一定不相交；
③如果两个链表都带环，就得重新写一个函数来判断，交点有两种位置：环内、环外。如果两条链表是在有环链表上相交，在环上选取一个节点点，遍历两条链表都会经过这个节点，可以以此来判断带环链表是否成环。
Node * CheckCycleCross(pNode list1, pNode list2)
{
pNode p1 = NULL;
pNode p2 = NULL;
pNode p3 = NULL;
pNode Cross = NULL;
int q1 = 0;
int q2 = 0;
assert(list1&&list2);
p1 = list1;
p2 = list2;
p3 = list2;
pNode meet = CheckCycle(list1);//检验是否成环，meet为相遇点。
if (meet == NULL)
{
printf("链表不成环\n");
return NULL;
}
while ((p3!=NULL)&&(p3!=meet))
{
p3 = p3->next;
}
if (p3 == NULL)
{
printf("链表不相交\n");//检验相交。若一个有环，一个无环，不用判断了，肯定两链表不相交；
//若两个都有环，判断第一个链表的碰撞点（fast与slow相遇的节点）是
//否出现在第二个链表的环中，如果在，则相交。
return NULL;
}
pNode entry = GetCycleEntryNode(list1, meet);//环的入口
while (p1->next != meet)
{
p1 = p1->next;
q1++;
}
while (p2->next != meet)
{
p2 = p2->next;
q2++;
}
int len1 = q1 + GetCircleLength(meet);//链表长度=环的头指针到交点长度+环的长度
int len2 = q2 + GetCircleLength(meet);
if (len1 > len2)
{
p1 = list1;
p2 = list2;
}
else
{
p1 = list2;
p2 = list1;
}
int diff = abs(len1 - len2);
for (int i = 0; i < diff; i++)
{
p1 = p1->next;
}
while (p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
Cross = p1;//交点
return p1;
}13.复杂链表的复制
一个链表的每个节点，有一个指向next指针指向下一个节点， 还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。
typedef struct ComplexNode
{
Datatype _data;
struct ComplexNode* _next;
struct ComplexNode* _random;
}ComplexNode,*pComplexNode;
首先得创立一个这样的链表，
接下来我们再创立一个链表，并且两个链表合并在一起
下一步就是下面这个链表的random指针都指向正确
然后再拆分链表
ComplexNode *Copy(pComplexNode *plist)//链表复制
{
pComplexNode cur = NULL;
pComplexNode cur1 = NULL;
pComplexNode tmp = NULL;
pComplexNode ret = NULL;
assert(plist != NULL);
cur = *plist;
while (cur)//创建新链表并且合并
{
tmp = (ComplexNode*)malloc(sizeof(ComplexNode));
tmp->_data = cur->_data;
tmp->_next = cur->_next;
cur->_next = tmp;
cur = cur->_next->_next;
}
cur = *plist;
while (cur)//合并之后的链表给新的节点连接_random
{
if (cur->_random != NULL)
{
cur->_next->_random = cur->_random->_next;
cur = cur->_next->_next;
}
else
{
cur->_next->_random = NULL;
cur = cur->_next->_next;
}
}
cur = *plist;
cur1 = cur->_next;
ret = cur1;
while (cur)//拆分链表
{
cur->_next = cur->_next->_next;
cur = cur1->_next;
if (cur == NULL)
break;//return ret;
cur1->_next = cur->_next;
cur1 = cur->_next;
}
return ret;
}14. 求两个有序单链表交集(差集)。
求两个链表的交集：让两个指p1 ,p2分别指向链表一和链表二，然后比较p1，p2指向节点的数据，如果p1的值小于p2的值，就让p1往后移一步，再次比较，反之就让p2往后移一步，再次比较；如果p1的值和p2的值相等把值则打印出来，再让两个指针都往后面移。
void UnionSet(pNode l1, pNode l2)
{
assert(l1&&l2);
while (l1&&l2)
{
if ((l1->data) < (l2->data))
{
l1 = l1->next;
}
else if ((l1->data) > (l2->data))
{
l2 = l2->next;
}
else
{
printf("%d ", l1->data);
l1 = l1->next;
l2 = l2->next;
}
}
printf("\n");
}如果想看完整的代码可以到我的Git账号下载：https://github.com/1214wuai/SeqListQuestion