0


【初阶数据结构与算法】第四篇:链表面试题详解

⭐️本篇博客我要给大家分享一下算法中的链表例题。希望对大家有所帮助。
⭐️ 博主码云gitee链接:码云主页


前言


🌏一、移除链表元素(传送门)

🍤给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

🔑思路:

    三种情况:常规情况,上面图中那种,还有就是连续的val,头就是val。

不管是哪种,就是pre和cur一个一个向后找,直到cur指向null,

当头是val的时候,free cur, 将head和cur移动到next


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    while(cur != NULL){
        //如果第一个就是val
        if(cur->val == val){
            struct ListNode* next = cur->next;
            //如果pre为空则要删除第一个节点
           if(pre != NULL){
                free(cur);
                pre->next = next;
                cur = next;
           }else{
               free(cur);
               head = next;
               cur = next;
           }
        //如果第一个不是val
        }else{
            pre = cur;
            cur = cur->next;
        }
    }
    return head;
}

🌏二、反转链表(传送门)

🍤给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

🔑思路1:

    定义三个指针![](https://img-blog.csdnimg.cn/0f092dbf89f641a1b558f16d57d9f2bf.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LyB6bmF5LiN5Y-r,size_20,color_FFFFFF,t_70,g_se,x_16)

首先要判断,head是不是NULL否则后面next指向空指针了

之后将cur->next指向pre,然后将cur和pre向后移动

此时移动next之前要判断是否,为空

则返回当前头指针pre即可

struct ListNode* reverseList(struct ListNode* head){
    //判断head和head->next是不是空,防止空指针
    if(head == NULL){
        return NULL;
    }
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = head->next;
    while(cur != NULL){
        cur->next = pre;
        pre = cur;
        cur = next;
        //next是不是空,防止空指针
        if(next != NULL){
            next = next->next;
        }
    }
    return pre;
}

🔑思路2:

创建一个新的头指针 newhead,将cur指向newhead,再将newhead移动到cur,将cur移动到next,移动next之前要判断是否为空

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

🌏三、链表的中间节点 (传送门)

🍤给定一个头结点为 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例 1:

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

🔑思路:

    运用快慢指针,将两个指针都从head开始,然后直到fast或者fast->next指向为空就找到了中间的节点了,**注意**,判断的时候,要注意fast->next要在fast之后,防止空指针
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //不能换位置,从左往右先判断,否则判断为空指针
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

🌏四、链表中倒数第K个节点(传送门)

🍤输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

🔑思路:

    依旧是利用快慢指针,首先,让fast移动K为,然后fast和slow之间的距离就是K,然后同时走,当fast为空的时候,slow指向的空间就是所求空间
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    //如果是空则返回空
    if(head == NULL){
        return NULL
    }
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(k--){
        fast = fast->next;
    }
    while(fast != NULL){
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

🌏五、合并两个有序链表(传送门)

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

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

🔑思路1:

    取一个初始为空的新链表,比较指向list1和指向list2的节点值,小的先放入新链表,之后,小的节点指针向后移动。当有一个指针为空时,就将另一个链表直接连接至新链表之后。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //分别判断list1和list2是否为空
    if(list1 == NULL){
        return list2;
    }
    if(list2 == NULL){
        return list1;
    }
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    while(list1 != NULL && list2 != NULL){
        if(list1-> val < list2-> val){
            //判断头是不是空
            if(tail == NULL){
                head = tail = list1;
            }else{
                tail->next = list1;
                tail = list1;
            }
            list1 = list1->next;
        }else{
            if(tail == NULL){
                head = tail = list2;
            }else{
                tail -> next = list2;
                tail = list2;
            }
            list2 = list2->next;
        }
    }
    //遍历完后有判断是否还有没有遍历的
    if(list1 != NULL){
        tail->next = list1;
    }
    if(list2 != NULL){
        tail->next = list2;
    }
    return head;
}

🔑思路2:

    思路1是不带哨兵的,下面写一个带哨兵的

    由于创建哨兵,所以不用判断list1和list2是否为空了,因为我们的返回值是head->next,返回的是头,而不是哨兵。

    最后记得释放内存

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //带哨兵位
    struct ListNode* head, *tail;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;

    while(list1 != NULL && list2 != NULL){
        if(list1-> val < list2-> val){
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }else{
            tail -> next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    //遍历完后有判断是否还有没有遍历的
    if(list1 != NULL){
        tail->next = list1;
    }
    if(list2 != NULL){
        tail->next = list2;
    }
    //为方便释放内存,提前记录头
    struct ListNode* list = head->next;
    free(head);
    //返回哨兵位下一位
    return list;
}

🌏六、链表分割(传送门)

🍤给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1:

输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]

🔑思路:

    新链表less和新链表greater,它们初始都为空。然后用指针cur遍历一遍原链表,小于x的节点放入less链表中,大于x的放入greater链表中,最后再将less和greater连接起来,返回less的头指针

    **当less不为空时,less最后的节点要指向greater的头节点。并且将greater最后节点的指针指向空。因为greater最后的指向可能指向less的某个节点,连接less和greater的时候就会形成死循环**
struct ListNode* partition(struct ListNode* head, int x){
    //less和greter分别为小于val和大于val的头指针
    struct ListNode* lesshead,  *lesstail, *greterhead, *gretertail;
    lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
    greterhead = gretertail = (struct ListNode*)malloc(sizeof(struct ListNode));
    //初始化
    lesstail->next = gretertail->next = NULL;
    struct ListNode* cur = head;
    while(cur != NULL){
        if(cur->val < x){
            lesstail->next = cur; 
            lesstail = lesstail->next;
        }else{
            gretertail->next = cur;
            gretertail = gretertail->next;
        }
        cur = cur->next;
    }
    lesstail->next = greterhead->next;
    //防止死循环
    gretertail->next = NULL;
    struct ListNode* list = lesshead->next;
    //防止内存泄漏
    free(lesshead);
    free(greterhead);
    return list;
}

🌏七、链表回文(传送门)

🍤给定一个链表的 头节点 head ,请判断其是否为回文链表。

如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。

示例 1:

输入: head = [1,2,3,3,2,1]
输出: true

🔑思路:

    找到中间节点,将它逆置之后,分别从head和rhead开始比较。

偶数情况:

奇数情况:

结果都一样,要注意的是反转之后,rhead节点的前一个指向的是rhead最后一个

//找中间节点
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //不能换位置,从左往右先判断,否则判断为空指针
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
//逆置
struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL){
        return NULL;
    }
    struct ListNode* cur = head;
    struct ListNode* next = cur->next;
    struct ListNode* newhead =NULL;
    while(cur != NULL){
        cur->next = newhead;
        newhead = cur;
        cur = next;
        if(next!=NULL){
            next = next->next; 
        }
    }
    return newhead;
}
bool isPalindrome(struct ListNode* head){
    struct ListNode* midhead = middleNode(head);
    struct ListNode* rhead = reverseList(midhead);

    while(head != NULL && rhead != NULL){
        if(head->val != rhead->val){
            return false;
        }
        head = head->next;
        rhead = rhead->next;
    }
    return true;
}

🌏八、相交链表(传送门)

🍤给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交:

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

🔑思路:

    先算出listA和listB长度,然后两个链表中较长的先走两者长度的差值,此时长的链表现在长度和短的一样,之后遍历如果发现相等则返回。

注意:编译器只会检查语法逻辑,执行逻辑不会检查,所以按照语法,我们要加上return,尽管没有返回从逻辑上来说

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    //第一个节点跳过,所以长度从一开始
    int lenA = 1;
    int lenB = 1;
    while(tailA->next != NULL){
        tailA = tailA->next;
        lenA++;
    }
    while(tailB->next != NULL){
        tailB = tailB->next;
        lenB++;
    }
    //尾节点是否相同
    if(tailA != tailB){
        return NULL;
    }
    //相交求交点,长的先走差值的步数,再一起走
    struct ListNode* shortlist = headB;
    struct ListNode* longlist = headA;
    if(lenA < lenB){
        shortlist = headA;
        longlist = headB;
    }
    int gap = abs(lenA-lenB);
    while(gap--){
        longlist = longlist->next;
    }
    while(shortlist != NULL && longlist != NULL){
        if(shortlist == longlist){
            return longlist;
        }
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    //执行逻辑没有问题,但是没有返回值的话会有语法逻辑
    return NULL;
}

🌏九、 环形链表(传送门)

🍤给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

🔑思路:

    快慢指针,如果在一个链表中,fast和slow能够相等,说明能找到,没有找到就说明没有环
bool hasCycle(struct ListNode *head) {
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

🌏环形指针扩展

🍤如果fast一次走两步,slow一次走一步,它们一次会相遇吗?

** 一定能!每次fast追击后,fast和slow距离减一**

🍤如果fast一次走3步,slow一次走1步,它们一次会相遇吗?

** 不一定,当两者距离是偶数一定能追上,因为每次fast和slow距离减少2,如果是奇数不行,fast会越过slow**

🍤如果fast一次走4步,slow一次走一步,它们一次会相遇吗?

** 一样的,只有fast和slow之间的距离是fast每次移动和slow缩小距离的整数倍就能**

🌏十、环形链表||(传送门)

🍤给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

🔑思路:

    先用快慢指针判断是否,有环,又环的话就记录快慢指针相遇的节点

设【链表头--入口点】L

【入口点--相遇点】X

【环的长度】C

慢指针走的路程为:L+X。

快指针走的路程为:L+X+C*N(其中N代表圈数,N>=1)。

快指针路程是慢指针路程的两倍

所以:L+X+CN=2(L+X)。(当L=10,C=2可以验证)

化简得:L=C*N-X

** L=C*(N-1)+(C-X)**

计算得出:

一个指针从head走,另一个指针从meet走,当两指针相等时,它们就指向环的入口点

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow = head, *fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            struct ListNode *meet = slow;
            //当meet和head相等的时候就是入口点
            while(meet != head){
                meet = meet->next;
                head = head->next;
            }
            return head;
        }
    }
    return NULL;
    
}

🌏十一、复制带随机指针的列表(传送门)

🍤例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

🔑思路:

    1.拷贝链表的每一个节点,将每个拷贝好的节点放在原节点后面

    2.将copy中的random变得和原节点一样

    3.拆解链表,把拷贝的链表从原链表中拆解出来

struct Node* copyRandomList(struct Node* head) {
    //1.拷贝链表并且将它放在原节点后面
    struct Node* cur = head;
    while(cur != NULL){
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->next = cur->next;
        cur->next = copy;
        copy->val = cur->val;
        cur = cur->next->next;
    }
    //2.将copy中random变为原节点一样
    cur = head;
    while(cur != NULL){
        struct Node* copy = cur->next;
        if(cur->random == NULL){
            copy->random = cur->random;
        }else{
            copy->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    //3.解开链表,构成原节点
    struct Node* copyhead = NULL, *copytail = NULL;
    cur = head;
    while(cur != NULL){
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(copyhead == NULL){
            copyhead = copytail = copy;
        }else{
            copytail->next = copy;
            copytail = copy;
        }
        cur->next = next;
        cur = next;
    }
    return copyhead;
}

🌏总结


本文转载自: https://blog.csdn.net/YQ20210216/article/details/123608084
版权归原作者 企鹅不叫 所有, 如有侵权,请联系我们删除。

“【初阶数据结构与算法】第四篇:链表面试题详解”的评论:

还没有评论