【数据结构初阶-oj】顺序表和链表的 oj 题（入门）

发布于：2023-01-20 ⋅ 阅读:(390) ⋅ 点赞:(0)

前言

上期详细讲解了 顺序表和链表，这期就来刷点题加深理解吧

对小白来说，很多思路也许给人感觉：“啊呀，这哪是碳基生物想得出来的！”

我也感同身受，所以停下狂奔的脚步，耐下心细细咀嚼顺序表、链表实现。旧题重做，很有一种清晰通透的爽快：

思路好像也没那么难想，实现起来也一气呵成了

本期概览

1.顺序表OJ

题目

题1 合并有序数组

在这里插入图片描述

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int p1 = 0;
    int p2 = 0;
    int* ans = (int*)malloc(sizeof(int) * (m+n));
    int i =  0;
    for(i=0; i<m+n; i++)
    {
        //谁小就尾插到ans，谁放完就放另一个
        if(p1 == m)//nums1拿完了
            ans[i] = nums2[p2++];//拿nums2
        else if(p2 == n)//nums2拿完了
            ans[i] = nums1[p1++];//拿nums1
        else if(nums1[p1] < nums2[p2])
            ans[i] = nums1[p1++];
        else
            ans[i] = nums2[p2++];
    }

    for(i=0; i<m+n; i++)
    {
        nums1[i] = ans[i];
    }
}
  • 需要考虑某一数组拿完的情况，否则会越界访问

来源：leetcode-88.

2.链表OJ

题目

题1 移除链表元素

image-20220811114058558

image-20220811114151510

  • 其实就是 指定删，但实现上有些容易出错的地方，分别看看吧

    • 带头单向非循环：

image-20220811115125960

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

    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = head;
    struct ListNode* pre = guard;
    struct ListNode* cur = head;

    while(cur)
    {
        struct ListNode* next = cur->next;
        //如果cur是要删除的结点
            //链接pre和next
        if(cur->val == val)
        {
            pre->next = next;
            free(cur);
            cur = next;
        }
        else
        {
            pre = cur;
            cur = cur->next;
        }
    }

    struct ListNode* tmp = guard->next;
    free(guard);
    return tmp;
}

  • 分析：

    • 带头则不需要考虑删除第一个结点的问题
    • 要释放guard，因此临时保存guard->next并返回

  • 不带头单向非循环：

image-20220811115911935

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = NULL;
    while(cur)
    {
        next = cur->next;
        if(cur->val == val)
        {
            if(prev == NULL)//头删直接改head
            {
                head = head->next;
            }
            else
            {
                prev->next = next;
                free(cur);
            }
            //移除元素不用动prev：如果 prev 被赋成 cur,等会 prev->next 就出问题
            cur = next;
        }
        else
        {
            prev = cur;
            cur = next;
        }
        
    }

    return head;
}
  • 分析：
    • 不带头需要考虑 删除第一个结点
    • 不能解引用 free 掉的指针

leetcode-203

题2 反转链表

image-20220811122810116

image-20220811123426229

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = NULL;
    while(cur)
    {
        next = cur->next;

        cur->next = prev;
        prev = cur;

        cur = next;
    }

    return prev;
}

leetcode-206

题3 链表的中间结点

在这里插入图片描述

思路1：
image-20220811105945038

  • 遍历的思路比较容易想到，但要考虑长度奇数还是偶数，时间复杂度也高，所以我们倾向探索更好的思路

思路2：
在这里插入图片描述

  • 快慢指针就很好地解决问题，时间复杂度低，而且实现也简单
  • 画出奇数和偶数长度的链表，发现
    • 奇数：stop: fast->next == NULL
    • 偶数：stop: fast == NULL
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;
}

来源：leetcode-876.链表的中间结点

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

image-20220812133847749
思路1：
在这里插入图片描述

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    struct ListNode* cur = pListHead;
    int n = 0;
    while(cur)
    {
        n++;
        cur = cur->next;
    }
    
    if(k > n || k == 0)
        return NULL;
    
    cur = pListHead;
    
    int gap = n-k;
    while(gap--)
    {
        cur = cur->next;
    }
    
    return cur;
}

思路2：
在这里插入图片描述

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    
    while(k--)
    {
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }
    
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}

来源：newcoder

题5 合并有序链表

image-20220811152358989

image-20220811152524182

  • 还需要考虑某一个链表没用完，剩了元素：谁没用完就把谁直接链接到新链表的尾部
  • 带头链表的重点：guard->next要置空，不然一切空指针情况都会出bug
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    //取小的尾插
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail = guard;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    guard->next = NULL;//考虑空链表情况
    while(cur1 && cur2)
    {
        if(cur1->val < cur2->val)
        {
            tail->next = cur1;
            tail = tail->next;
            cur1 = cur1->next;
        }
        else
        {
            tail->next = cur2;
            tail = tail->next;
            cur2 = cur2->next;
        }
    }

    //如果是list1没尾插完
    if(cur1)
    {
        tail->next = cur1;
    }
    //如果是list2没尾插完
    if(cur2)
    {
        tail->next = cur2;
    }

    struct ListNode* newhead = guard->next;//链表为空这里出问题
    free(guard);
    return newhead;
}

来源：leetcode-21.

题6 链表分割

image-20220811153152661

image-20220811155144653

  • 链接是这道题容易疏忽的地方：
    • 带头链表的初始化
      • less_guard->next = NULL;
      • greater_guard->next = NULL;
    • 结果链表的尾部指向空
ListNode* partition(ListNode* pHead, int x) 
    {
        //小于x，放到less；其他放到greater
        struct ListNode* less_guard = (struct ListNode*)malloc(sizeof(ListNode));
        struct ListNode* greater_guard = (struct ListNode*)malloc(sizeof(ListNode));
        less_guard->next = NULL;//应对空链表
        greater_guard->next = NULL;//应对空链表
        struct ListNode* less_tail = less_guard;
        struct ListNode* greater_tail = greater_guard;
        struct ListNode* cur = pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                less_tail->next = cur;
                less_tail = less_tail->next;
            }
            else
            {
                greater_tail->next = cur;
                greater_tail = greater_tail->next;          
            }
            
            cur = cur->next;
        }
        //链接：尾要指向空
        less_tail->next = greater_guard->next;
        greater_tail->next = NULL;
        
        struct ListNode* newhead = less_guard->next;
        free(less_guard);
        free(greater_guard);
        return newhead;
    }

来源：newcoder

题7 链表的回文结构

image-20220812133826545

image-20220812134027352

  • 前面的 中间结点 和 逆置链表 如果掌握扎实，这道题的思路会自动浮现在你脑海了
  • 如果没有时间复杂度的要求，更简单的思路就是 逆置整个链表，和原链表对比
bool chkPalindrome(ListNode* phead) 
    {
        //找中间结点
        struct ListNode* fast = phead;
        struct ListNode* slow = phead;
        struct ListNode* mid = NULL;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        mid = slow;
        
        //逆置后半部分
        struct ListNode* prev = NULL;
        struct ListNode* next = NULL;
        while(mid)
        {
            next = mid->next;
            mid->next = prev;
            prev = mid;
            mid = next;
        }
        
        //此时prev指向逆置的后半部的头
        
        //两边向中间遍历对比
        while(prev)
        {
            if(phead->val != prev->val)
                return false;
            
            phead = phead->next;
            prev = prev->next;
        }
        
        return true;
    }

来源：newcoder

题8 相交链表

image-20220812092105191

image-20220812134706303

image-20220812134728406

  • 做来做去都是操作一下链表指针呢
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //长的先走gap步
        //计算长度
    int lenA = 0;
    int lenB = 0;
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    while(curA)
    {
        lenA++;
        curA = curA->next;
    }
    while(curB)
    {
        lenB++;
        curB = curB->next;
    }

    int gap = abs(lenA-lenB);
        //假设A长
    struct ListNode* fast = headA;
    struct ListNode* slow = headB;
        //否则B长
    if(lenB > lenA)
    {
        fast = headB;
        slow = headA;
    }
    while(gap--)
    {
        fast = fast->next;
    }

    //一起走：next相同就相交
    while(fast)//fast slow 都一样
    {
        if(fast == slow)
            return fast;
        if(fast->next == slow->next)
            return fast->next;
        fast = fast->next;
        slow = slow->next;
    }

    return NULL;
}

来源：leetcode-160.

题9 环形链表

image-20220812095547224

image-20220812100739961

  • 这题还是快慢指针：如果有环，fast先进环，slow后进环，最终fast套了 N(N>=0)圈后相遇
bool hasCycle(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)
            return true;
    }

    return false;
}

来源：leetcode-141.

题10 环形链表2

image-20220812101042140
思路1：
image-20220812105809941

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //长的先走gap步
        //计算长度
    int lenA = 0;
    int lenB = 0;
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    while(curA)
    {
        lenA++;
        curA = curA->next;
    }
    while(curB)
    {
        lenB++;
        curB = curB->next;
    }

    int gap = abs(lenA-lenB);
        //假设A长
    struct ListNode* fast = headA;
    struct ListNode* slow = headB;
        //否则B长
    if(lenB > lenA)
    {
        fast = headB;
        slow = headA;
    }
    while(gap--)
    {
        fast = fast->next;
    }

    //一起走：next相同就相交
    while(fast)//fast slow 都一样
    {
        if(fast == slow)
            return fast;
        if(fast->next == slow->next)
            return fast->next;
        fast = fast->next;
        slow = slow->next;
    }

    return NULL;
}

struct ListNode *detectCycle(struct ListNode *head) 
{
    //有环，快慢指针肯定有相遇点，相遇点肯定在圈内
    //1.从相遇点断开，cycle_cut = meet->next; meet->next = NULL
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* meet = NULL;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            break;
    }
    if(fast == NULL || fast->next == NULL)
        return NULL;
        //断开
    struct ListNode* cycle_cut = fast->next;
    fast->next = NULL;

    //2.看head和cycle_cut是否相交
    struct ListNode* entryNode = getIntersectionNode(head, cycle_cut);

    return entryNode;

}

思路2：
在这里插入图片描述

struct ListNode *detectCycle(struct ListNode *head) 
{
    //slow 从 head 走，fast 从 meet 走，套N圈后在入口相遇
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* meet = NULL;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            break;
    }

    if(fast == NULL || fast->next == NULL)
        return NULL;

    slow = head;
    while(slow)
    {
        if(slow == fast)
            return slow;
        slow = slow->next;
        fast = fast->next;
    }

    return NULL;
}

来源：leetcode-142.

题11 链表的深度拷贝

image-20220812113859818

在这里插入图片描述

思路1：
image-20220812134414869

思路2：

在这里插入图片描述

struct Node* copyRandomList(struct Node* head) 
{
    //1.插新链表并拷贝值
    struct Node* cur = head;
    struct Node* copy = NULL;
    struct Node* next = 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;
    }

    //2.拷贝新链表的random
    cur = head;
    while(cur)
    {
        copy = cur->next;
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;
        cur = copy->next;
    }

    //3.断开新链表和原链表，新链表链接起来（用尾插的方式）
    cur = head;
    struct Node* copyHead = NULL;
    struct Node* copyTail = NULL;
    while(cur)
    {
        copy = cur->next;
        next = copy->next;

        //尾插
        if(copyHead == NULL)
        {
            copyHead = copy;
            copyTail = copyHead;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }

        //恢复原链表
        cur->next = next;

        cur = cur->next;
    }

    return copyHead;
}

来源：leetcode-138.

本期分享就到这啦，不足之处望请斧正

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布