【数据结构】链表经典oj

🍍一、链表的回文结构

🍍二、输入两个链表，找出第一个相交节点

思路一（暴力解法）

思路二（时间复杂度更优解）

🍍三、判断链表中是否有环

🍉思路

🍉拓展

🍍一、链表的回文结构

以下面这个链表为例子：

由于单向链表是不可往前回朔的，所以我们无法将从后往前对比。

我们可以将后面半段，先反转一次。

再通过两个指针进行对比，第二个指针是链表的中间节点，我们需要找到这个中间节点。

接下来附上两段代码，

寻找中间节点：


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

反转链表：


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode * prev,*cur,*next=NULL;
    prev=NULL;
    cur=head;
    next=NULL;
    while(cur)
    {
        next=cur->next;
        cur->next=prev;
        //迭代
        prev=cur;
        cur=next;
    }
    return prev;
}

上面这两个代码实直接从前面的题目摘下来的，链表的题目的背景一般是一样的，因此是适用的。

答案如下：


struct ListNode* middleNode(struct ListNode* head)
        {
        struct ListNode *slow=head,*fast=head;
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
          }
    
    
        struct ListNode* reverseList(struct ListNode* head){
        struct ListNode * prev,*cur,*next=NULL;
        prev=NULL;
        cur=head;
        next=NULL;
        while(cur)
        {
            next=cur->next;
            cur->next=prev;
            //迭代
            prev=cur;
            cur=next;
        }
        return prev;
        }
        bool chkPalindrome(ListNode* A) 
        {
            ListNode *p1=A;
            ListNode *mid=middleNode(A);
            ListNode *p2=reverseList(mid);
            while(p1&&p2)
            {
                if(p1->val!=p2->val)
                    return false;
                p1=p1->next;
                p2=p2->next;
            }
            return true;
         }

🍍二、输入两个链表，找出第一个相交节点

思路一（暴力解法）

原链表我们可以表达如一下形式

想要找到c1节点，我们只需要在b链表中查找a链表中第一个与b链表的共同节点。


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *pa=headA,* pb=headB;
    while(pb)
    {
        pa=headA;
        while(pa)
        {
            if(pb==pa)
            return pb;
            pa=pa->next;
        }
        pb=pb->next;
    }
    return NULL;
}

思路二（时间复杂度更优解）

我们现将这两个链表便利一遍，得到两个链表的长度，然后再将长的那个链表先走几步，这个步数为这两个链表的长度之差。

变成下面这样，这样再次将两个链表遍历，遇到的第一个相同节点就是答案。


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *pa=headA,*pb=headB,* cura=headA,* curb=headB;
    int lena=1,lenb=1;
    while(cura->next!=NULL)
    {
        lena++;
        cura=cura->next;
    }
     while(curb->next!=NULL)
    {
        lenb++;
        curb=curb->next;
    }
    if(cura!=curb)//要是两个链表的尾结点不相同的话说明不是相交链表
        return NULL;
    if(lenb>lena)
    {
        for(int i=1;i<=lenb-lena;i++)
        {
            pb=pb->next;
        }
    }
    else
        {
        for(int i=1;i<=lena-lenb;i++)
        {
            pa=pa->next;
        }
    }
    while(pa!=pb)
    {
        pa=pa->next;
        pb=pb->next;
    }
    return pa;
}

这就是两个方法的差距：

🍍三、判断链表中是否有环

题目中的环指的是如下图的一个节奏，这个链表在实际应用中是没什么用的，这里只是为了用来锻炼我们的思维。

🍉思路

设置快慢指针，要是原本走在前面的指针都能与慢指针碰面，就说明快指针陷入了循环。

这一题里我们指能将快指针速度设置为慢指针的二倍（后面会有讲解）。


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