【数据结构】单链表OJ题（二）

文章来源地址https://uudwc.com/A/Pd6Nz

?博客主页：小王又困了

?系列专栏：数据结构

?人之为学，不日近则日退

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

一、链表分割

?方法一：

二、链表的回文

?方法一：

三、相交链表

?方法一：

四、环形链表

?方法一：

?️前言：

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

一、链表分割

题目：

?方法一：

我们创建两条链表，把小于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;
}

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