淘先锋技术网

首页 1 2 3 4 5 6 7

🔥博客主页:小王又困了

📚系列专栏:数据结构

🌟人之为学,不日近则日退 

❤️感谢大家点赞👍收藏⭐评论✍️


目录

一、链表分割

💡方法一:

二、链表的回文

💡方法一: 

三、相交链表

💡方法一: 

四、环形链表

 💡方法一: 


🗒️前言:

在上一期中我们给大家介绍了单链表,也了解了单链表的实现。接下来就让我们进入实践,练习一些经典题目,让我们对单链表的理解更加深入

一、链表分割

题目:

💡方法一:

我们创建两条链表,把小于x的节点放在一条链表中,剩余的放在另一条节点,最后将两条链表连接起来。在这里要使用带哨兵位的链表,不用考虑头插和第一条链表为空的问题,可以大大减少代码量。

 注意:要将链表最后一个节点的指针域置为空,不然会导致链表循环。

ListNode* partition(ListNode* pHead, int x) 
{
    struct ListNode* lhead ,*ltail,*ghead,*gtail;
    ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));
    lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur=pHead;
    while(cur)
    {
         if(cur->val<x)
         {
             ltail->next=cur;
             ltail=ltail->next;
         }
         else  
         {
              gtail->next=cur;
              gtail=gtail->next;
         }
         cur=cur->next;
    }


    ltail->next=ghead->next;
    gtail->next=NULL;

    struct ListNode* head=lhead->next;
    free(ghead);
    free(lhead);

    return head;
}

二、链表的回文

题目:

💡方法一: 

我们先找到中间节点,然后将后面的节点反转,分别从头节点和中间节点开始比较,如果两两节点的数据域有一对不相等,返回flase;如果都相等返回true。

class PalindromeList {
  public:
  //找中间节点
    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;
    }

    //反转链表
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* cur = head;
        struct ListNode* newnode = NULL;
        while (cur) {
            //保存节点
            struct ListNode* next = cur->next;

            //头插
            cur->next = newnode;
            newnode = cur;
            cur = next;
        }
        return newnode;
    }
    bool chkPalindrome(ListNode* head) 
    {   
        struct ListNode* mid=middleNode(head);
        struct ListNode* rmid=reverseList(mid);

        struct ListNode* cur=head;
        while(rmid&&cur)
        {
            if(rmid->val!=cur->val)
            {
                return false;
            }
            else 
            {
                rmid=rmid->next;
                cur=cur->next;
            }
            
        }
        return true;
    }
};

三、相交链表

题目:

💡方法一: 

在做这道题,我们可以分为两步:

1.判断是否相交:

        遍历两条链表,比较最后一个节点的地址,地址相等,说明两条链表相交。

2.找起始节点:

        先计算出两条链表的长度,计算出它们的差值,让长的链表先走差距步,然后两条链表一起走,相等时返回的就是相交的起始节点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* curA=headA,*curB=headB;
    int lenA=1,lenB=1;
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    if(curA->next!=curB->next)
    {
        return NULL;
    }

    //求两链表的差距
    int gap=abs(lenA-lenB);

    struct ListNode* longlist=headA,*shortlist=headB;
    if(lenA<lenB)
    {
        longlist=headB;
        shortlist=headA;
    }
    //长链表先走差距步
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}

四、环形链表

题目:

 💡方法一: 

 当我们定义快慢指针,快指针一次走两步,慢指针一次走一步。如果链表存在环,在进入环中快指针一定可以追上慢指针。因为每走一步距离就减1,当减到0时就追上了。

  • 假设起点到入口点距离为L
  • 假设环的周长为C
  • 假设入口点到相遇点的距离为X

我们通过快慢指针走过的路程来判断,但在这里要注意环的周长很小时,所以在这里要考虑两种情况: 

情况一:slow进环后一圈之内,fast一定追上slow

  • slow走的距离:L+X
  • fast走的距离:L+C+X

情况二:slow进环时,fast已经走了n圈

  • slow走的距离:L+X
  • fast走的距离:L+nC+X 

由于快指针速度使慢指针的二倍,所以快指针走的路程也是慢指针的二倍。由此可得出:

结论:慢指针从起点开始走,快指针从相遇点开始走,它们最终会相遇在入口点。

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* slow,* fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
            struct ListNode* meet=fast;
            while(head!=meet)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}

本次的内容到这里就结束啦。希望大家阅读完可以有所收获,同时也感谢各位读者三连支持。文章有问题可以在评论区留言,博主一定认真认真修改,以后写出更好的文章。你们的支持就是博主最大的动力。