几个常见的链表面试题<一>

今天看了几个常见的链表面试题，整理出来和大家分享一下，有错误的地方还请大家能够予以指正，不胜感激。

1.单链表实现约瑟夫环

ListNode* JosephusProblem(ListNode* hus,size_t k)
{
ListNode* man,*next;
assert(hus);
man = hus;

while (man->next != man)//直到剩下一个人终止循环
{
    size_t count = k;
    //走了k步
    while (--count)//此处需要注意用前置——
    {
        man = man->next;
    }
    //删掉轮到的这个人
    next = man->next;
    man->data = next->data;
    man->next = next->next;

    free(next);

}

return man;

}
void Test2()
{
ListNode* pplist = NULL;
ListNode* tail = NULL;

PushBack(&pplist, 1);
PushBack(&pplist, 2);
PushBack(&pplist, 3);
PushBack(&pplist, 4);
PushBack(&pplist, 5);

printList(pplist);

tail = FindNode(pplist,5);
tail->next = pplist;

printf("%d\n", JosephusProblem(pplist, 3)->data);

}
测试结果如下：

2.逆置单链表
首先要定义三个结构体指针

void ReverseList(ListNode** ppNode)
{
ListNode* n0 = NULL,*n1=*ppNode,*n2=(*ppNode)->next;
if (*ppNode == NULL)
return;
while (n1)
{
n1->next = n0;
n0 = n1;
n1 = n2;
if (n2)
n2 = n2->next;
}
*ppNode = n0;
}
void Test3()
{
ListNode* pplist = NULL;

PushBack(&pplist, 1);
PushBack(&pplist, 2);
PushBack(&pplist, 3);
PushBack(&pplist, 4);
PushBack(&pplist, 5);

printList(pplist);

ReverseList(&pplist);
printList(pplist);

}
测试结果如下：

3.求倒数第k个节点，只能遍历一遍链表

ListNode* Find_k_Node(ListNode* ppList,size_t k)
{
ListNode* slow =ppList,*fast=ppList;
//先让fast走k-1步
while (–k)
{
if (fast == NULL)
return NULL;
fast = fast->next;
}
//同时走，直到fast走到最后一个节点
while (fast->next)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
void Test4()
{
ListNode* pplist = NULL;

PushBack(&pplist, 1);
PushBack(&pplist, 2);
PushBack(&pplist, 3);
PushBack(&pplist, 4);
PushBack(&pplist, 5);

printList(pplist);

printf("%d\n", Find_k_Node(pplist,2)->data);

}这里写代码片
测试结果如下：以求倒数第2个节点为例

*未完待续。。。。。