【刷题系列】链表经典OJ题-网络知识

文章题目来源力扣或牛客
🎈力扣（LeetCode）全球极客挚爱的技术成长平台
LeetCode官网：https://leetcode-cn.com/problem-list/e8X3pBZi/
牛客网-笔试题库：https://www.nowcoder.com

✨目录

移除链表元素
反转链表
链表的中间节点
链表中倒数第k个结点
合并两个有序链表
链表分割
回文链表
相交链表
环形链表丨
环形链表II
复制带随机指针的链表

1.移除链表元素

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-linked-list-elements

✨思路一
可以依次遍历链表，将不是val值的元素尾插到新的节点中
时间复杂度：O(N)
空间复杂度：O(1)

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*newhead=NULL,*tail=NULL,*cur=head;
    while(cur)
    {
        if(cur->val!=val)//把不是val的尾插到newhead中
        {
            if(tail==NULL)
            {
                tail=newhead=cur;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;    
            }
        }
        cur=cur->next;
    }
    //最后tail置空
    if(tail!=NULL)
    	tail->next=NULL;
    return newhead;
}

✨思路二
直接在原链表中删除，遇到val直接释放，让它的前一个指向val的后一个
时间复杂度：O(N)
空间复杂度：O(1)

struct ListNode* removeElements(struct ListNode* head, int val){
    if(head==NULL)
    return NULL;


    struct ListNode*newNode=(struct ListNode*)malloc(sizeof(struct ListNode));//设置一个新的头结点
    newNode->next=head;
    struct ListNode*cur=newNode;
    while(cur->next)
    {
        if((cur->next)->val==val)//删val元素
        {
            struct ListNode *del=cur->next;
            cur->next=del->next;
            free(del);
        }
        else
        {
            cur=cur->next;
        }
    }
    cur=newNode->next;
    free(newNode);
    return cur;
}

2.反转链表

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list

✨思路一
依次遍历链表头插
时间复杂度：O(N)
空间复杂度：O(1)

struct ListNode* reverseList(struct ListNode* head){

    //头插法
    struct ListNode* cur=head,*next=NULL,*newhead=NULL;
    while(cur)
    {
        next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;
}

✨思路二
直接在原地修改指针指向
时间复杂度：O(N)
空间复杂度：O(1)

struct ListNode* reverseList(struct ListNode* head){
    //原地修改
    struct ListNode*n1=NULL,*n2=head;
    while(n2)
    {
        struct ListNode*n3=n2->next;
        n2->next=n1;
        n1=n2;
        n2=n3;
    }
    return n1;
}

3.链表的中间节点

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/middle-of-the-linked-list

✨思路一（不推荐）
遍历一遍求出链表长度，长度除2后，再重新让指针走中间节点
✨思路二（推荐）
快慢指针法，定义两个指针，fast，slow，让fast一次走两步，slow一次走一步，fast走到NULL，slow就是中间节点

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

4.链表中倒数第k个结点

来源：牛客网
链接：oj链接

✨思路
有上题的铺垫，我们也可以用快慢指针，，定义两个指针，fast，slow，只不过这次先让fast走k步，然后fast和slow一起走，fast为NULL,slow就是倒数第K个节点

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    if(pListHead==NULL)
        return NULL;
    struct ListNode*fast=pListHead,*slow=pListHead;
    while(k--)//先让fast走k步
    {
    	//预防K很大，fast已经为空
        if(fast==NULL)
            return NULL;
        fast=fast->next;
    }
    //同时走
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

5.合并两个有序链表

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-sorted-lists

✨思路
依次遍历两个链表取小的尾插到新的头
时间复杂度：O(N)
空间复杂度：O(1)

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

    struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位
    newhead->next=NULL;
    struct ListNode*cur1=list1,*cur2=list2,*tail=newhead;
    while( cur1 && cur2 )//取小尾插
    {
        if(cur1->val  > cur2->val)
        {
            tail->next=cur2;
            cur2=cur2->next;
        }
        else
        {
            tail->next=cur1;
            cur1=cur1->next;
        }
        tail=tail->next;
    }
    if(cur1)//把剩下的连上
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }

    tail=newhead->next;
    free(newhead);
    return tail;
}

6.链表分割

来源：牛客网
链接：OJ链接

✨思路
遍历链表，把链表分成两条，一个全是小于x的，剩下的就是另一个链表，然后两个链表再拼接在一起

在这里插入图片描述

    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        //设置两个哨兵位,head1存比x大的，head2存比x小的进行尾插
    struct ListNode* head1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct ListNode));
        head1->next=NULL,head2->next=NULL;
     struct ListNode* cur = pHead, * tail1 = head1, * tail2 = head2;
    while(cur)
    {
        if(cur->val < x)//取小的尾插到head2中
        {
            tail2->next=cur;
            tail2=tail2->next;
        }
        else//取大的尾插到head1中
        {
            tail1->next=cur;
            tail1=tail1->next;
        }
        cur=cur->next;
    }
        //将两部分连接，并将尾节点的next置空
        tail2->next=head1->next;
         tail1->next = NULL;
        pHead=head2->next;
        free(head1);
        free(head2);
        
        return pHead;
    }

7.回文链表

来源：牛客网
链接：OJ链接

✨思路
先找到中间节点，把后半部分逆置，然后再依次比较是否相等

struct ListNode* reverseList(struct ListNode* head){

    struct ListNode*n1=NULL,*n2=head;
    while(n2)
    {
        struct ListNode*n3=n2->next;
        n2->next=n1;
        n1=n2;
        n2=n3;
    }
    return n1;
}
    struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*slow=head,*fast=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid=middleNode(A);//找中间节点
        struct ListNode*cur2=reverseList(mid);//从中间节点开始逆置
        struct ListNode*cur1=A;
        while(cur2)//依次比较
        {
            if(cur1->val!=cur2->val)
                return false;
            cur2=cur2->next;
            cur1=cur1->next;
        }
        
        return true;
    }

8.相交链表

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists

✨思路
仔细观察可以发现，如果链表相交的话，那么它们都有一个共同的特点，那就是尾节点相同，所以可以利用这个特点来解决链表是否相交
至于返回相交点，我们可以依次算出每一个链表的长度，然后让长的那个一个先走差距步，然后再同时走，直到相等即为相交点

在这里插入图片描述

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

    struct ListNode* cur1=headA,*cur2=headB;
    int count1=1,count2=1;
    //找尾
    while(cur1->next)
    {
        cur1=cur1->next;
        count1++;
    }
    while(cur2->next)
    {
        cur2=cur2->next;
        count2++;
    }
    //尾节点不相等则不相交
    if(cur1!=cur2)
        return NULL;

    struct ListNode*longList=headA,*shotList=headB;
    if(count1 < count2 )
    {
        longList=headB;
        shotList=headA;
    }
    int k=abs(count1-count2);
    //让长的先走差距步
    while(k--)
    {
        longList=longList->next;
    }
    //相等地方即为入口
    while(longList!=shotList)
    {
        longList=longList->next;
        shotList=shotList->next;
    }
    return longList;

}

9.环形链表丨

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle

✨思路
快慢指针法：定义两个指针fast和slow，fast一次走两步，slow一次走一步，最后如果相等则说明存在环，如果fast遇到NULL，则说明没有环
证明：

bool hasCycle(struct ListNode *head) {
    struct ListNode*fast,*slow;
    fast=slow=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
            return true;
    }
    return false;
}

10.环形链表 II

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle-ii

✨思路一
快慢指针法：定义两个指针fast和slow，fast一次走两步，slow一次走一步，相等位置为相遇点，在相遇点断开，转化成两个链表相交求交点问题

在这里插入图片描述

✨思路二
这个解法很妙，就是从找到相遇点后，一个指针从相遇点开始，另一个指针从头开始，同时遍历，直到相等就是入环点，这个可以用数学公式证明

在这里插入图片描述

//思路二的代码实现
struct ListNode *detectCycle(struct ListNode *head) {
        struct ListNode*fast,*slow;
    fast=slow=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)//有环
        {
            struct ListNode*cur=head;
            while(cur!=slow)//入口点
            {
                cur=cur->next;
                slow=slow->next;
            }
            return cur; 
        }
    }
     return NULL;

}

11.复制带随机指针的链表

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/copy-list-with-random-pointer

✨思路
这题主要的难点在于随机指针random的复制，搞定了这个随机指针，那么问题就迎刃而解了
首先，我们可以把每一个复制节点的尾插到每一个原节点的后面，然后依次根据原节点的random把复制节点的random连接上，最后再恢复原链表，取复制链表

在这里插入图片描述

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head,*next=head,*copy=NULL;
    //复制节点尾插到原节点中
    while(cur)
    {
        next=cur->next;
        copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        
        //迭代
        cur=next;
    }
	//复制randam
    cur=head;
    while(cur)
    {
        copy=cur->next;
        next=cur->next->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        //迭代
        cur=next;
    }

    //恢复原链表
    struct Node*copyhead=NULL,*tail=NULL;
    cur=head;
    while(cur)
    {
        copy=cur->next;
        next=cur->next->next;
        if(copyhead==NULL)
        {
            copyhead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }
        cur->next=next;
        //迭代
        cur=next;
    }
    return copyhead;
}

在这里插入图片描述

1.移除链表元素

2.反转链表

3.链表的中间节点

4.链表中倒数第k个结点

5.合并两个有序链表

6.链表分割

7.回文链表

8.相交链表

9.环形链表丨

10.环形链表 II

11.复制带随机指针的链表

相关文章

央媒谈“文盲演员”引发饭圈甩锅大战

野生大熊猫深夜遛达 镜头前呆萌打卡

张萌谈演员到底需不需要有文化

情人节多地迎领证高峰

婚房烂尾10年业主住进毛坯房

多地首套房贷利率降至4%以下 为什么急于提前还贷

野生大熊猫深夜遛达镜头前呆萌打卡

多地首套房贷利率降至4%以下为什么急于提前还贷