开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 链表常见面试题 -> 正文阅读

[数据结构与算法]链表常见面试题

链表面试题

在这里插入图片描述

文章目录

链表面试题
前言
一、删除链表中等于给定值 val 的所有节点。
二、反转一个单链表。
三、给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
四、输入一个链表，输出该链表中倒数第k个结点。
五、将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
六、编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
七、链表的回文结构。
八、两个链表相交问题
九、链表判环问题
总结

前言

一、删除链表中等于给定值 val 的所有节点。

题目链接

思路：分三种情况讨论；

1.链表为空，直接返回空链表。

2.链表第一个节点值是val

那么很容易想到把头结点释放掉，直接头指针指向next。
或许你会这样写：

 if(head!=NULL&&head->val == val)
    {
        head = head->next;
    }

思路正确，但是！！！你要注意你保证删除了原来的头结点，但是现在的头结点值是否还是val呢？？或者测试样例给你连续几个相同的节点，而你就只考虑了第一个这时候第二个就会被忽略！！

3.其他节点是val
此时我们已经确保头结点值不是val了，只需要往后判断
在这里插入图片描述
如果第二个节点值是val，那么只需前一个结点指向第三个节点，释放掉第二个节点即可。这里注意一旦第三个节点为空也适用。只需要这样用两个指针 cur 和 next 依次判断，直到next不是空为止。

代码：

struct ListNode* removeElements(struct ListNode* head, int val){
    if(head == NULL)
    {
        return NULL;
    }
    while(head!=NULL&&head->val == val)
    {
        head = head->next;
    }
    struct ListNode* cur = head;
    struct ListNode* next = NULL;
    while(cur!=NULL&&cur->next!= NULL)
    {
        next = cur->next;
        if(next->val == val)
        {
            cur->next = next->next;
            
            next = next->next;
        }
        else
        {
            cur = cur->next;
            next = next->next;
        }
    }
    return head;
}

二、反转一个单链表。

题目地址

思路：首先这道题你可以偷懒去交换节点的值，太没水平不做赘述。那么这道题正常怎么做呢？我们去把整个链表给他拆下来，节点虽然麻烦，但是我们改变指针方向轻松。
首先用cur指针指向链表头结点，next指向下一个。把cur指针改变方向去指向NULL，接下来cur回到链表上next往下走，再把2节点指向1。依次遍历来达到翻转。

代码如下（示例）：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL,*next = NULL;
    while(cur)
    {
        next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

代码如下（示例）：

data = pd.read_csv(
    'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
print(data.head())

三、给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

题目链接

思路一：先遍历一遍链表求出长度 N。如果N是奇数直接在遍历N/2次知道中间节点，如果N是偶数，返回第N/2+1个节点。操作简单，代码省略。
思路二：双指针。动图如下：

fast指针一次走两步，slow指针一次走一步。


struct ListNode* middleNode(struct ListNode* head){
   
    struct ListNode*slow = head,*fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

四、输入一个链表，输出该链表中倒数第k个结点。

题目链接

思路一：人人都能想到的正常遍历，遍历一遍求长度，再来一遍求倒数第k个结点。思路简单，代码省略。
思路二：仍然是双指针。注意双指针解决问题应用很多，可以大大提高效率。那么方法就是想让fast指针走k步，接着两个指针一起一次一步往后走，直到fast为空，那么此时slow的位置正好是倒数第K个节点。（或者fast指针先走k-1步，接着依次往后直到fast指向最后一个节点，此时slow也指向倒数第K个节点，原理都一样）

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // 这里我才用走k-1步的方法
    struct ListNode* slow =pListHead,*fast = pListHead;
    k--;
    while(k--&&fast)
    {
        fast = fast->next;
    }
     if(fast == NULL)
            return NULL;//防止k大于链表长度
    while(fast->next)//fast下一个为空也就是fast指向尾节点
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

五、将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

题目链接

思路：首先注意给的数据都是有序从小到大排列的，而我们要做到的就是创建一个新的链表，不断把两个链表合并并且要保持有序。
那么要保持有序就得把两个链表数值比较，用两个指针指向两个链表，比较之后，小的节点合并到新链表，指针指向下一个，另一个不操作。直到链表为空。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1==NULL)return l2;
    if(l2==NULL)return l1;//如果其中一个链表为空直接返回另一个
    struct ListNode* head =NULL,*p = NULL;
    if(l1->val <= l2->val)
    {
        head = l1;
        l1 = l1->next;
    }
    else
    {
        head = l2;
        l2 = l2->next;
    }
    p = head;//首先确定好新链表头结点
    while(l1 && l2)//只要指向两个链表指都不是空继续判断
    {
        if(l1->val <= l2->val)//l1值小合并到新链表
        {
            p->next = l1;
            l1 = l1->next;
        }
         else//l2值小合并到新链表
        {
            p->next = l2;
            l2 = l2->next;
        }
        p=p->next;
    }
    if(l1)//如果l1指针没有指向空，而此刻已经出了循环说明l2是空遍历结束，此时只需要把l1剩下的直接链接到新的聊表尾部
    {
        p->next = l1;
    }
    else if(l2)//同上
    {
        p->next = l2;
    }

    return head;

}

六、编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

题目链接

思路：我们新开辟两个两个链表，一个用来存放小于x的结点，另一个存放大于或等于x的结点，最后把两个链表连在一起。如下：

这里假设x = 3，需要注意这里排序之后5和最后一个2还是链接在一起的，对于big这个链表需要在原来链表遍历之后把最后节点next置空！！！！

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        // write code here
        struct ListNode*lessHead,*greaterHead,*lessTail,*greaterTail;
         lessHead = (ListNode*)malloc(sizeof(ListNode));
        lessTail = lessHead;//小的节点
        lessTail->next = NULL;
         greaterHead = (ListNode*)malloc(sizeof(ListNode));
         greaterTail = greaterHead;//大数节点
        greaterTail->next = NULL;  
        struct ListNode* cur = pHead;
        while(cur)//开始遍历
        {
            if(cur->val < x)//小于x放到小的链表里
            {
                lessTail->next = cur; 
                lessTail = lessTail->next;
            }
            else//大于等于x放到大的链表里
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;   
            }
            cur = cur->next;   
        }
        lessTail->next = greaterHead->next;
        //这里注意lessTail->next要指向greaterHead->next，因为greaterHead是头结点不存放数！!
        struct ListNode* newnode = lessHead->next;//同理lessHead是头结点不存放数
                greaterTail->next = NULL;//这里注意尾节点一定要置空否则就可能出现上边的情况！！
        free(lessHead);
        free(greaterHead);   
    return newnode;
    }          
};

七、链表的回文结构。

题目链接
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路：这道题需要注意啊，时间复杂度为O(n),额外空间复杂度为O(1)。这也就说明了正常思路，说把给的链表逆置过来这种做法空间复杂度就达到O(N),是不允许的！
那么怎么做呢?
既然不让翻转整体那我们就翻转一半，先用快慢指针法找到中点；再将中点之后的链表反转；原链表中点前一个成员指向空；原链表循环比较反转链表，若有不同则返回false，若成功执行到最后返回true.这里逆置，找中间元素前边有讲解不再赘述。

在这里插入图片描述

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL,*next = NULL;
    while(cur)
    {
        next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}
struct ListNode* middleNode(struct ListNode* head){
   
    struct ListNode*slow = head,*fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* middle = middleNode(A);
        struct ListNode* rHead = reverseList(middle);
        struct ListNode* curA = A;
        struct ListNode* curR = rHead;
        while(curA && curR)
        {
            if(curA->val != curR->val)
            {
                return false;
            }
            else
            {
                curA = curA->next;
                curR = curR->next;
            }
        }
        return true;
    }
};

八、两个链表相交问题

题目链接

首先你要知道两个链表相交，并不是链表交叉

而是从有交点开始，就一直相同,如下图这种Y型结构。
那么第一个问题：判断两个链表是否成环，也就是两个链表是否相交？
如果你在想那简单，暴力算法挨个比较两个链表中是否有相同节点，那么做法就太复杂了。
其实你只需要判断两个链表的尾节点是否相同就能判断。
其次判断出是否相交之后，我们怎么找到第一个相同的节点？
其实你要注意，相交的链表尾部都是相同，从相交开始，长度数据都一样。因此我们只需要遍历两个链表求出两个长度M 和 N，再让两个指针指向两个头节点，让长的链表指针先走M和N的差，这样再让两个指针依次往后走，返回相等的节点就是第一个。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int lena=0,lenb=0;
    struct ListNode *taila = headA,*tailb = headB;
    while(taila)
    {
        taila=taila->next;
        lena++;
    }
    while(tailb)
    {
        tailb=tailb->next;
        lenb++;
    }
    
   if(taila == tailb)
    {
        
        if(lena > lenb)
        {
            int n = lena-lenb;
            while(n--)
            {
                headA = headA->next;
            }
        }
        else if(lenb > lena)
        {
            int n = lenb-lena;
            while(n--)
            {
                headB = headB->next;
            }
        }
        int min = lena > lenb ? lenb:lena;
        while(min--)
        {
            if(headB == headA)
            {
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }


    }

    return NULL;

}

九、链表判环问题

题目链接
在这里插入图片描述
抽象如图：

思路：用快慢指针。对于一个有环的链表，遍历最终都会进入都环里。那么问题来了，或许你直接想到fast每次走2步，slow每次走一步。那不知道你有没有想过为什么走两步，走三步行吗？四步呢？
那么接下来看这张图，假设快指针每次走3步，满指针一次走1步，那么很显然永远不能相遇！！！由于环的长度你并不知道，因此3步4步不可取！！！而构成一个环至少长度是2，当你快指针走2步时，每一次比满指针快走一步，而环长>=2永远是1的倍数，因此一旦有环，总会相交。
那么怎么找到第一次相交的节点？让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    while(fast&&fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            struct ListNode *meet = fast;

            while(meet!=head)
            {
                meet = meet->next;
                head = head->next;
               
            }
            return meet;
        }
    }
    return NULL;
    
}