链表面试题

程序员文章站 2022-05-06 11:04:41

...

1.从头到尾打印单链表
链表面试题

递归法：（递归深度到NULL之后一次返回，将其打印出来）
- 当第一个结点 pFirst==NULL 时返回（也是递归的出口）
- 递归调用
- 访问每次递归时的结点
循环法：
- 记录第一个结点（作为循环结束条件）
- 一次遍历至最后一个结点将其访问
- 将最后一个结点的位置标志向前移动
- 再次循环遍历到最后一个结点将其访问

//递归法
void ReversePrintDG(SList *pFirst)
{
    if (pFirst == NULL){
        printf("NULL <-");
        return;
    }
    ReversePrintDG(pFirst->pNext);
    printf("%2d <-", pFirst->data);
}
//循环
void ReversePrintLoop(SList *pFirst)
{
    SList *pEnd = NULL;
    SList *pNode = pFirst;
    while (pEnd != pFirst){
        pNode = pFirst;
        while (pNode->pNext != pEnd){
            pNode = pNode->pNext;
        }
        printf("%2d <-", pNode->data);
        pEnd = pNode;
    }
    printf("\n");
}

2.逆置链表
链表面试题

定义三个变量SList *p1 = NULL, *p2 = *ppFirst, *p3 = p2->pNext;
在循环中进行赋值交换p2->pNext = p1; p1 = p2; p2 = p3;

void ReverseLoop(SList **ppFirst)
{
    assert(ppFirst);
    if ((*ppFirst) == NULL){
        return ;
    }
    SList *p1 = NULL, *p2 = *ppFirst, *p3 = p2->pNext;
    while (p2 != NULL){
        p2->pNext = p1;
        p1 = p2;
        p2 = p3;
        if (p3 != NULL){
            p3 = p3->pNext;
        }
    }
    *ppFirst = p1;
}

3.删除一个无头单链表的非尾节点（不能遍历链表）
//pPos 不是尾结点
链表面试题

void RemoveNoFirstNode(SList *pPos)
{
    assert(pPos != NULL);
    assert(pPos->pNext != NULL);
    SList *pNext = pPos->pNext;
    pPos->data = pNext->data;
    pPos->pNext = pNext->pNext;
    free(pNext);
}

4.在无头单链表的一个节点前插入一个节点（不能遍历链表）
链表面试题

void InsertNoFirstNode(SList **ppPos, DataType data)
{
    assert(ppPos != NULL);
    if (*ppPos == NULL){
        PushFront(ppPos, data);
        return;
    }
    SList *pPos = *ppPos;
    SList *pNode = BuyNewNode(pPos->data);
    pPos->data = data;
    pNode->pNext = pPos->pNext;
    pPos->pNext = pNode;
}

5.单链表实现约瑟夫环(JosephCircle)
（1）一群人围在一起坐成环状（如：N）
（2）从某个编号开始报数（如：K）
（3）数到某个数（如：M）的时候，此人出列，下一个人重新报数
（5）一直循环，直到所有人出列，约瑟夫环结束
链表面试题

先把链表构成一个环
找到要杀死的那个人，虽然要杀是循环K次，但是要更改链表，要找前一个，所以K-1
将其杀死
将其起始位置指向杀死的下一个人

SList *JosephCircle(SList *pFirst, int k)
{
    //把无循环构成有循环
    SList *pNode; 
    for (pNode = pFirst; pNode->pNext != NULL; pNode = pNode->pNext){

    }
    pNode->pNext = pFirst;
    SList *pCurrent = pFirst;
    SList *pPrev = NULL;
    int n;
    while (pCurrent->pNext != pCurrent){ //1.只剩一个
        n = k;
        while (--n > 0){  //2.虽然要杀是循环K次，但是要更改链表，要找前一个，所以K-1
            pPrev = pCurrent;//需要保存前一个
            pCurrent = pCurrent->pNext;
        }
        //3.kill
        pPrev->pNext = pCurrent->pNext;
        free(pCurrent);
        //4.指向原来的下下个，但现在的下一个
        pCurrent = pPrev->pNext;
    }
    return pCurrent;
}

void Swap(DataType *a, DataType *b)
{
    DataType tmp = *a;
    *a = *b;
    *b = tmp;
}

6.冒泡排序

void Swap(DataType *a, DataType *b)
{
    DataType tmp = *a;
    *a = *b;
    *b = tmp;
}

SList *BubbleSort(SList *pFirst)
{
    if (pFirst == NULL){
        return NULL;
    }
    SList *pEnd = NULL;
    SList *pOp1 = pFirst;
    SList *pOp2 = pFirst->pNext;
    int isChange = 0;
    while (pEnd != pFirst->pNext){
        isChange = 0;
        pOp1 = pFirst;
        pOp2 = pFirst->pNext;
        while (pOp2 != pEnd){
            if (pOp1->data > pOp2->data){
                Swap(&(pOp1->data), &(pOp2->data));
                isChange = 1;
            }
            pOp1 = pOp1->pNext;
            pOp2 = pOp2->pNext;
        }
        if (isChange == 0){
            break;
        }
        pEnd = pOp1;
    }
    return pFirst;
}

7.合并两个有序链表,合并后依然有序

建立两个变量分别标记在两个链表的头
依次遍历链表，让链表元素进行比较，小的元素将标记向后移动一个，将原先标记的小元素插入新链表中
循环上面操作直到一个链表遍历完（NULL），然后将为遍历完的链表后面元素链接在新链表后面
打印出新链表

SList *MergeSortedList(SList *pOneFirst, SList *pTwoFirst)
{
    SList *pOneNode = pOneFirst, *pTwoNode = pTwoFirst;
    SList *pRemain = pOneNode;
    SList *pResult, *pNode;

    Init(&pResult);
    while (pOneNode != NULL && pTwoNode != NULL){
        if (pOneNode->data < pTwoNode->data){
            PushBack(&pResult, pOneNode->data);
            pOneNode = pOneNode->pNext;
        }
        else{
            PushBack(&pResult, pTwoNode->data);
            pTwoNode = pTwoNode->pNext;
        }
    }
    if (pOneNode == NULL){
        pRemain = pTwoNode;
    }
    else{
        pRemain = pOneNode;
    }
    for (pNode = pRemain; pNode != NULL; pNode = pNode->pNext){
        PushBack(&pResult, pNode->data);
    }
    return pResult;
}

8.求两个已排序单链表中相同的数据

建立两个变量分别标记在两个链表的头
依次遍历链表，让链表元素进行比较，小的元素将标记向后移动一个
然后比较两个标记点的元素，如果元素的数据域相等，将任意一个元素放入新链表
将两个标记都向后移动一位，直至一个链表为空结束遍历

SList *UnionSet(SList *pOneFirst, SList *pTwoFirst)
{
    SList *pOneNode = pOneFirst, *pTwoNode = pTwoFirst;
    SList *pResult;

    Init(&pResult);
    while (pOneNode != NULL && pTwoNode != NULL){
        if (pOneNode->data < pTwoNode->data){
            pOneNode = pOneNode->pNext;
        }
        else if (pOneNode->data > pTwoNode->data){
            pTwoNode = pTwoNode->pNext;
        }
        else if(pOneNode->data = pTwoNode->data){
            PushBack(&pResult, pOneNode->data);
            pOneNode = pOneNode->pNext;
            pTwoNode = pTwoNode->pNext;
        }
    }
    return pResult;
}

9.查找单链表的中间节点，要求只能遍历一次链表

分别定义一个快慢指针
让快指针走两步，慢指针走一步
返回慢指针，即：单链表的中间结点

SList *FindMiddle(SList *pFirst)
{
    SList *pFast = pFirst;
    SList *pSlow = pFirst;
    while (pFirst != NULL && pFirst->pNext != NULL && pFirst->pNext->pNext){
        pSlow = pSlow->pNext;
        pFirst = pFirst->pNext->pNext;
    }
    return pSlow;
}

10.查找单链表的倒数第k个节点，要求只能遍历一次链表

分别定义一个快慢指针
让快指针先走K步
然后快慢指针每次走一步
返回慢指针，即：单链表的倒数第K个结点

SList *FindDSK(SList *pFirst, int k)
{
    SList *pFront = pFirst;
    SList *pBack = pFirst;
    int i;
    for (i = 0; i < k-1; i++){
        pFront = pFront->pNext;
    }
    while (pFront->pNext != NULL){
        pFront = pFront->pNext;
        pBack = pBack->pNext;
    }
    return pBack;
}

11.判断两个链表是否相交，若相交，求交点。（假设链表不带环)

//判断相交
int HasCross(SList *pOneFirst, SList *pTwoFirst)
{
    if (pOneFirst == NULL || pTwoFirst == NULL){
        return 0;
    }
    SList *pOne = pOneFirst;
    SList *pTwo = pTwoFirst;
    for (; pOne->pNext != NULL; pOne = pOne->pNext){

    }
    for (; pTwo->pNext != NULL; pTwo = pTwo->pNext){

    }
    if (pOne == pTwo){
        return 1;
    }
    else
        return 0;
}

//计算长度
static int __GetListLength(SList *pFirst)
{
    SList *pNode;
    int r = 0;
    for (pNode = pFirst; pNode != NULL; pNode = pNode->pNext){
        r++;
    }
    return r;
}

//相交前两段链表的长度差
static int __GetDiff(int lengthOne, int lengthTwo)
{
    int diff;
    if (lengthOne > lengthTwo){
        diff = lengthOne - lengthTwo;
    }
    else{
        diff =  lengthTwo -lengthOne;
    }
    return diff;
}

//返回交点
static SList *GetCrossPoint(SList *pOneFirst, SList *pTwoFirst)
{
    int lengthOne = __GetListLength(pOneFirst);
    int lengthTwo = __GetListLength(pTwoFirst);
    SList *pShortFirst = pOneFirst;
    SList *pLongFirst = pTwoFirst;
    int i;
    int diff = __GetDiff(lengthOne, lengthTwo);
    SList *pLong, *pShort;
    if (lengthOne > lengthTwo){
        SList *pShortFirst = pTwoFirst;
        SList *pLongFirst = pOneFirst;
    }
    pLong = pLongFirst;
    pShort = pShortFirst;
    for (i = 0; i < diff-1; i++){
        pLong = pLong->pNext;
    }
    while (pLong != pShort){
        pLong = pLong->pNext;
        pShort = pShort->pNext;
    }
    return pLong;
}

相关标签：链表面试题数据结构 C语言

上一篇：常见链表面试题解题思路

下一篇：链表面试题

链表面试题

java 数据结构单链表的实现

Java描述数据结构学习之链表的增删改查详解

你可能不熟练的十个前端HTML5经典面试题

C#如何自定义线性节点链表集合

Oracle的四道经典面试题分享

PHP小教程之实现链表

PHP小教程之实现双向链表

详解java数据结构与算法之双链表设计与实现

C#实现基于链表的内存记事本实例

Java常见面试题之多线程和高并发详解