/*****/单链表常见面试题

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

...

1.比较顺序表和链表的优缺点，说说它们分别在什么场景下使用？

1）顺序表支持随机访问，单链表不支持随机访问。
2）顺序表插入/删除数据效率很低，时间复杂度为O(N)（除尾插尾删），单链表插入/删除效率更高，时间复杂度为O(1)。
3）顺序表的CPU高速缓存效率更高，单链表CPU高速缓存效率低。

2.从尾到头打印单链表
逆序打印单链表（递归）
/*****/单链表常见面试题
代码：
List.h

#pragma once
#include<assert.h>
typedef int DataType;

typedef struct SListNode
{
    DataType data;
    struct SListNode* next;

} SListNode;

//从尾到头打印单链表
void PrintTailToHead(SListNode* pList)
{
    if (pList == NULL)
        return;

    PrintTailToHead(pList->next);//子链表
    printf("%d ", pList->data);

}
SListNode* BuyNode(DataType x)
{
    SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    node->data = x;
    node->next = NULL;

    return node;
}

void PrintList(SListNode* pHead)
{
    SListNode* cur = pHead;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void PushBack(SListNode** pHead, DataType x)
{
    assert(pHead);
    if (*pHead == NULL)
    {
        *pHead = BuyNode(x);
    }
    else
    {
        SListNode* cur = *pHead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = BuyNode(x);
    }
}

void PrintSList(SListNode*& pHead, DataType x)
{
    SListNode* cur = pHead;
    while (cur)
    {
        printf("%d", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void TestList()
{
    SListNode* list = NULL;
    PushBack(&list, 1);
    PushBack(&list, 2);
    PushBack(&list, 3);
    PushBack(&list, 4);
    PrintList(list);
    PrintTailToHead(list);
}

test.cpp

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include"List.h"
int main()
{

    TestList();
    system("pause");
    return 0;
}

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

代码：
List.h

#pragma once
#include<assert.h>
typedef int DataType;

typedef struct SListNode
{
    DataType data;
    struct SListNode* next;

} SListNode;

***//删除一个无头单链表的非尾节点（替换法删除）
void EraseNonTail(SListNode* pos)
{
    //assert(pos);
    //assert(pos->next);
      assert(pos && pos->next);
    SListNode* next = pos->next;
    pos->data = next->data;
    pos->next = next->next;
    free(next);
}***

SListNode* Find(SListNode*  pHead, DataType x)
{
    SListNode* cur = pHead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
SListNode* BuyNode(DataType x)
{
    SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    node->data = x;
    node->next = NULL;

    return node;
}
void PrintList(SListNode* pHead)
{
    SListNode* cur = pHead;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void PushBack(SListNode** pHead, DataType x)
{
    assert(pHead);
    if (*pHead == NULL)
    {
        *pHead = BuyNode(x);
    }
    else
    {
        SListNode* cur = *pHead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = BuyNode(x);
    }
}

void PrintSList(SListNode*& pHead, DataType x)
{
    SListNode* cur = pHead;
    while (cur)
    {
        printf("%d", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void TestList()
{
    SListNode* list = NULL;
    PushBack(&list, 1);
    PushBack(&list, 2);
    PushBack(&list, 3);
    PushBack(&list, 4);
    PrintList(list);

    SListNode* pos = Find(list, 3);
    EraseNonTail(pos);
    PrintList(list);
}

test.cpp

#include<stdio.h>
#include<malloc.h>
#include"List.h"
int main()
{

    TestList();
    return 0;
}

/*****/单链表常见面试题
4.在无头单链表的一个非头节点前插入一个节点

//在无头单链表非头结点前插入新结点
    /*void InsertNotHeadNode(PNode pos, DataType _data)
    {
        if (NULL == pos)
        {
            return;
        }
        PNode newNode = BuyNode(pos->data);
        if (newNode)
        {
            newNode->next = pos->next;
            pos->next = newNode;
            pos->data = _data;
        }
    }*/

5.单链表实现约瑟夫环(JosephCircle)
/*****/单链表常见面试题

PNode JosephCircle(PNode pHead, size_t M)
{
    if (NULL == pHead)
    {
        return NULL;
    }
    PNode pCur = pHead;
    PNode prev = pCur;
    while (pCur != pCur->next)
    {
        size_t k = M;
        while (--k)
        {
            pCur = pCur->next;
        }
        PNode pDel = pCur->next;
        pCur->data = pDel->data;
        pCur->next = pDel->next;
        free(pDel);
    }
    return pCur;
}

6.逆置/反转单链表
/*****/单链表常见面试题

逆置单链表--三个指针
PNode ReverseList(PNode pHead)
{
    if (NULL == pHead || NULL == pHead->next)
    {
            return pHead;
    }
    PNode prev = pHead;
    PNode pCur = prev->next;
    PNode pnext = pCur->next;
    while (pnext)
    {
        pCur->next = prev;
        prev = pCur;
        pCur = pnext;
        pnext = pnext->next;
    }
    pCur->next = prev;
    pHead->next = NULL;
    return pCur;
}

/*****/单链表常见面试题

PNode ReverseList(PNode pHead)
{
    if (NULL == pHead || NULL == pHead->next)
    {
            return pHead;
    }
    PNode pCur = pHead->next;
    PNode newNode = NULL;
    while (pCur)
    {
        pHead->next = newNode;
        newNode = pHead;
        pHead = pCur;
        pCur = pCur->next;
    }
    pHead->next = newNode;
    newNode = pHead;
    return newNode;
}

7.单链表排序（冒泡排序&快速排序）
冒泡（升序）：
void BubbleSort(PNode pHead) { if (NULL == pHead || NULL == pHead->next) { return ; } PNode pCur = pHead; PNode pTail = NULL; int flag = 0; while (pTail != pHead) { pCur = pHead; while (pCur->next != pTail) { if (pCur->data > pCur->next->data) { DataType tmp = pCur->data; pCur->data = pCur->next->data; pCur->next->data = tmp; flag = 1; } pCur = pCur->next; if (!flag) { return ; } } pTail = pCur; } }

8.合并两个有序链表,合并后依然有序
/*****/单链表常见面试题

PNode MergeList(PNode pHead1, PNode pHead2)
{
    if (NULL == pHead1)
    {
        return pHead2;
    }
    if (NULL == pHead2)
    {
        return pHead1;
    }
    PNode newNode = NULL;
    PNode pTail = NULL;
    if (pHead1->data < pHead2->data)
    {
        pTail = pHead1;
        pHead1 = pHead1->next;
    }
    else
    {
        pTail = pHead2;
        pHead2 = pHead2->next;
    }
    newNode = pTail;
    while (pHead1 && pHead2)
    {
        if (pHead1->data < pHead2->data)
        {
            pTail->next = pHead1;
            pTail = pHead1;
            pHead1 = pHead1->next;
        }
        else
        {
            pTail->next = pHead2;
            pTail = pHead2;
            pHead2 = pHead2->next;
        }
    }
    if (pHead1)
    {
        pTail->next = pHead1;
    }
    else
    {
        pTail->next = pHead2;
    }
    return newNode;
}

9.查找单链表的中间节点，要求只能遍历一次链表
/*****/单链表常见面试题

代码：
List.h

#pragma once
#include<assert.h>
typedef int DataType;

typedef struct SListNode
{
    DataType data;
    struct SListNode* next;

} SListNode;

//找中间节点
SListNode* FindMidNode(SListNode* list)
{
    if (list == NULL)
        return NULL;
    SListNode* slow = list, *fast = list;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
SListNode* BuyNode(DataType x)
{
    SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    node->data = x;
    node->next = NULL;

    return node;
}

void PrintList(SListNode* pHead)
{
    SListNode* cur = pHead;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void PushBack(SListNode** pHead, DataType x)
{
    assert(pHead);
    if (*pHead == NULL)
    {
        *pHead = BuyNode(x);
    }
    else
    {
        SListNode* cur = *pHead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = BuyNode(x);
    }
}
void TestList()
{
    SListNode* list = NULL;
    PushBack(&list, 1);
    PushBack(&list, 2);
    PushBack(&list, 3);
    PushBack(&list, 4);
    PushBack(&list, 5);
    PushBack(&list, 6);
    PrintList(list);

    SListNode* mid = FindMidNode(list);
    printf("Mid:%d\n", mid->data);
}

test.cpp

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include"List.h"
int main()
{

    TestList();
    system("pause");
    return 0;
}

/*****/单链表常见面试题
10.查找单链表的倒数第k个节点，要求只能遍历一次链表

PNode FindLastKNode(PNode pHead, size_t K)
{
    if (NULL == pHead || K == 0)
    {
        return NULL;
    }
    PNode pSlow = pHead;
    PNode pFast = pHead;
    while (--K)
    {
        if (NULL == pFast)
        {
            return NULL;
        }
        pFast = pFast->next;
    }
    while (pFast->next)
    {
        pSlow = pSlow->next;
        pFast = pFast->next;
    }
    return pSlow;
}

11.删除链表的倒数第K个结点
/*****/单链表常见面试题

PNode DeleteLastKNode(PNode pHead, size_t K)
{
    if (NULL == pHead || K == 0)
    {
        return NULL;
    }
    PNode pos = FindLastKNode(pHead,K);
    Erase(&pHead,pos);
}

12.判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复杂度&空间复杂度。
/*****/单链表常见面试题

#pragma once
#include<assert.h>
typedef int DataType;

typedef struct SListNode
{
    DataType data;
    struct SListNode* next;

} SListNode;
SListNode* BuyNode(DataType x)
{
    SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    node->data = x;
    node->next = NULL;

    return node;
}


void PushBack(SListNode** pHead, DataType x)
{
    assert(pHead);
    if (*pHead == NULL)
    {
        *pHead = BuyNode(x);
    }
    else
    {
        SListNode* cur = *pHead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = BuyNode(x);
    }
}

SListNode* Find(SListNode* pHead, DataType x)
{
    SListNode* cur = pHead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
//判断链表带环
bool IsCircle1(SListNode* pHead)
{
    SListNode* fast, *slow;
    fast = slow = pHead;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}
SListNode* IsCircle(SListNode* pHead)
{
    SListNode* fast, *slow;
    fast = slow = pHead;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (slow == fast)
        {
            return slow;
        }
    }
    return NULL;
}
//求环的长度
size_t GetCircleLen(SListNode* meetNode)
{
    assert(meetNode);
    int count = 1;
    SListNode* cur = meetNode->next;
    while (cur != meetNode)
    {
        cur = cur->next;
        ++count;
    }
    return count;
}


//求环的入口点
SListNode* GetCircleEntry(SListNode* pHead, SListNode* meetNode)
{
assert(pHead && meetNode);
while (pHead && meetNode)
{
    if (pHead == meetNode)
    {
        return meetNode;
    }
    pHead = pHead->next;
    meetNode = meetNode->next;
}
return NULL;
}


//判断两个链表是否相交，若相交，求交点。（假设链表不带环）
//判相交
bool CheckIsMeet(SListNode* list1, SListNode* list2)
{
    if (list1 == NULL || list2 == NULL)
    {
        return false;
    }
    SListNode* tail1 = list1;
    SListNode* tail2 = list2;

    while (tail1->next)
    {
        tail1 = tail1->next;
    }
    while (tail2->next)
    {
        tail2 = tail2->next;
    }

    if (tail1 == tail2)
    {
        return true;
    }
    else
    {
        return false;
    }
}


SListNode* GetMeetNode(SListNode* list1, SListNode* list2)
{
    SListNode* cur1 = list1;
    SListNode* cur2 = list2;

    int len1 = 0, len2 = 0;
    while (cur1)
    {
        len1++;
        cur1 = cur1->next;
    }
    while (cur2)
    {
        len2++;
        cur2 = cur2->next;
    }

    SListNode* longList = list1, *shortList = list2;
    if (len1 < len2)
    {
        longList = list2;
        shortList = list1;
    }
    int gap = abs(len1 - len2);
    while (gap--)
    {
        longList = longList->next;
    }
    while (longList)
    {
        if (longList == shortList)
        {
            return longList;
        }
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}
void PrintList(SListNode* pHead)
{
    SListNode* cur = pHead;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
void TestList()
{
    SListNode* list = NULL;
    PushBack(&list, 1);
    PushBack(&list, 2);
    PushBack(&list, 3);
    PushBack(&list, 4);
    PushBack(&list, 5);
    PushBack(&list, 6);
    PrintList(list);


    SListNode* list2 = NULL;
    PushBack(&list2, 1);
    PushBack(&list2, 2);
    PushBack(&list2, 3);
    PushBack(&list2, 4);
    PushBack(&list2, 5);
    PushBack(&list2, 6);
    PrintList(list2);


    SListNode* entry = Find(list, 4);
    SListNode* tail = Find(list, 6);
    tail->next = entry;

    SListNode* meetNode = IsCircle(list);
    //assert(meetNode);
    //assert(entry == GetCircleEntry(list, meetNode));
    SListNode* entrynode = GetCircleEntry(list, meetNode);
    printf("入口点%p\n",meetNode);
    //printf("是否带环%p\n",meetNode);
    printf("%d\n", IsCircle1(list));
    //size_t len = GetCircleLen(meetNode);
    //SListNode* node = GetMeetNode(list,list2);
}

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

14.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】
/*****/单链表常见面试题

/*****/单链表常见面试题

//如果两个链表都不带环  
int NotCycleCheckCross(pLinkNode head1,pLinkNode head2)  
{  
    pLinkNode list1 = head1->next;  
    pLinkNode list2 = head2->next;  
    if ((NULL==list1 )||(NULL==list2))  
    {  
        return 0;      //不相交  
    }  
    while (NULL != list1->next)  
    {  
        list1 = list1->next;  
    }  
    while (NULL != list2->next)  
    {  
        list2 = list2->next;  
    }  
    if (list1==list2)  
    {  
        return 1;      //相交  
    }  
    return 0;          //不相交  
}  

//链表带环，判断两个链表是否相交  
int CycleCheckCross(pLinkNode meet1, pLinkNode meet2)  
{  
    pLinkNode cur = meet1->next;  
    if (meet1 == meet2)  
    {  
        return 1;     //链表相交  
    }  
    while ((cur != meet1)&&(cur!=meet2))  
    {  
        cur = cur->next;  
    }  
    if (cur == meet2)  
    {  
        return 1;   //链表相交  
    }  
    return 0;       //不相交  
}  


//将上面两个函数封装成一个函数  
int CheckCross(pLinkNode head1, pLinkNode head2)          //参数为两个头结点  
{  
    pLinkNode fast = NULL;  
    pLinkNode slow = NULL;  
    pLinkNode meet1 = NULL;  
    pLinkNode meet2 = NULL;  
    if (head1->next == NULL || head2->next == NULL)  
    {  
        return 0;          //至少一个链表为空链表，则两个链表一定不相交  
    }  
    fast = head1->next;  
    slow = head1->next;  
    while (fast&&fast->next)           //判断链表head1是否带环  
    {  
        fast = fast->next->next;  
        slow = slow->next;  
        if (fast == slow)  
        {  
            meet1 = fast;  
            break;  
        }  
    }  
    fast = head2->next;  
    slow = head2->next;  
    while (fast&&fast->next)           //判断链表head2是否带环  
    {  
        fast = fast->next->next;  
        slow = slow->next;  
        if (fast == slow)  
        {  
            meet2 = fast;  
            break;  
        }  
    }  
    if ((meet1 == NULL) && (meet2 == NULL))       //如果两个链表都不带环  
    {  
        return NotCycleCheckCross(head1, head2);  
    }  
    else if (meet1&&meet2)                        //如果两个链表都带环  
    {  
        return CycleCheckCross(meet1, meet2);  
    }  
    //如果两个链表一个带环一个不带环，则一定不相交直接返回0  
    return 0;            //不相交  
}

15.复杂链表的复制。一个链表的每个节点，有一个指向next指针指向下一个节点，还有一个Sibling指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表，返回复制后的新链表。
/*****/单链表常见面试题

新建一个头结点，先不考虑Sibling，将整个单链表复制一份。然后寻找每个结点的Sibling所指向的位置。以寻找2这个结点的Sibling为例：设置一个计步器count，然后以游标指针cur遍历整个链表，如果cur的地址等于2这个结点的Sibling，则寻找成功，这时在新链表中走上count步所找到的结点就是我们要找的结点。这个方法效率最低。

pLinkNode CloneComplexLinklist(pLinkNode head)  
{  
    pLinkNode cur = head->next;  
    if (NULL == head->next)         //判断是不是空链表  
    {  
        return NULL;  
    }  
    pLinkNode newNode= NULL;  
    pLinkNode newhead = NULL;  
    CreateNode(&newhead, cur->data);  
    pLinkNode last= newhead;          //新建一个头结点  
    cur = cur->next;  
    while (NULL != cur)                //复制整个链表  
    {  
        CreateNode(&newNode, cur->data);  
        last->next = newNode;  
        cur = cur->next;  
        last = last->next;  
    }  
    cur = head->next;  
    pLinkNode p = newhead;  
    int s = 0;                           //计步器  
    //链接Sibling  
    while (NULL != cur)   
    {  
        last = head->next;  
        while (cur->Sibling&&cur->Sibling != last)  //找到当前结点cur的Sibling在旧链表中的位置  
        {  
            s++;  
            last = last->next;  
        }  
        //如果这个位置不为空  
        if (NULL != cur->Sibling)  
        {  
            last=newhead;  
            while (s>0)                //寻找cur所对应结点p的Sibling在新链表中的位置  
            {  
                s--;  
                last=last->next;  
            }  
            p->Sibling = last;            //链接p的Sibling  
        }  
        cur = cur->next;  
        p = p->next;  
    }  
    return newhead;                    //返回头结点  
}

16.求两个已排序单链表中相同的数据。void UnionSet(Node* l1, Node* l2);

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

下一篇：常见的单链表面试题——进阶篇

/*****/单链表常见面试题

java 数据结构单链表的实现

10个最常见的HTML5面试题附答案

java实现单链表增删改查的实例代码详解

Python实现数据结构线性链表（单链表）算法示例

java单链表逆序用法代码示例

JavaScript中最常见的三个面试题解析

Python常见面试题分享！面试题中的No1！

js常见面试题

关于单链表的排序问题

如何用JavaScript实现功能齐全的单链表详解

/*****/单链表常见面试题

java 数据结构单链表的实现

10个最常见的HTML5面试题 附答案

java实现单链表增删改查的实例代码详解

Python实现数据结构线性链表（单链表）算法示例

java单链表逆序用法代码示例

JavaScript中最常见的三个面试题解析

Python常见面试题分享！面试题中的No1！

js常见面试题

关于单链表的排序问题

如何用JavaScript实现功能齐全的单链表详解

10个最常见的HTML5面试题附答案