淘先锋技术网

首页 1 2 3 4 5 6 7

在这里插入图片描述
今天继续分享我们关于链表的OJ题。
第一题
在这里插入图片描述
合并升序链表

这道题我们可以这样理解,首先是不带哨兵位,我们先给一个head和tail指针,然后第一个链表和第二个链表进行比较,如果list1的数据比list2的数据大的时候,我们就尾插到head中,但是因为我们链表没有哨兵位,所以要考虑是否为空的情况,当我们head不为空的时候,先尾插,然后更新list和tail的位置,往后移动,直到一个链表为空的时候,结束,再把不是空的链表中的数据插入到链表当中去。

那我们来写这道题吧。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
        if(list1==NULL)
        {
            return list2;
        }
        if(list2==NULL)
        {
            return list1;
        }
        //如果链表一个为空,就直接返回不是空的链表。

        struct ListNode*head;
        struct ListNode*tail;
        tail=NULL;
        head=NULL;
        while(list1 && list2)
        {
            if(list1->val>list2->val)
            {
                if(head==NULL)
                {
                    head=tail=list2;
                    //head为空的时候,一个数据也没有

                }
                else
                {
                //插入数据,更新tail
                    tail->next=list2;
                    tail=tail->next;
                    
                }
                //放入数据list要更新
                list2=list2->next;
                
            }
            else
            {
               if(tail==NULL)
                {
                    head=tail=list1;
                    
                }
                else
                {
                    tail->next=list1;
                    tail=tail->next;
                    
                }
                list1=list1->next;
            }
        }
        //一个为空的话就退出。然后把不是空的放入就行了。
        if(list1==NULL)
        {
            tail->next=list2;
        }
        if(list2==NULL)
        {
            tail->next=list1;
        }
        return head;
}

上面的代码是没有哨兵位的,这题其实有一个哨兵位可能反而简单一点,让我们来看看有哨兵位的情况吧。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
        if(list1==NULL)
        {
            return list2;
        }
        if(list2==NULL)
        {
            return list1;
        }

        struct ListNode*head=( struct ListNode*)malloc(sizeof(struct ListNode));
        head->next=NULL;
       struct ListNode* tail=head;
        while(list1 && list2)
        {
            if(list1->val>list2->val)
            {
                tail->next=list2;
                tail=tail->next;
                list2=list2->next;
            }
            else
            {
                tail->next=list1;
                tail=tail->next;
                list1=list1->next;
            }
        }
        if(list1==NULL)
        {
            tail->next=list2;
        }
        if(list2==NULL)
        {
            tail->next=list1;
        }
        struct ListNode*next=head->next;
        free(head);
        return next;
}

代码明显简单一点了,其实也是差不多的,就是有哨兵位不用判断第一个节点是否是空,直接放入就行了。

题目二
添加链接描述
在这里插入图片描述

这道题目我们创建两个带哨兵位的链表来存放,比它大的放在一个链表中,小的在放到另一个链表当中,最后进行链接就行了。我们来看代码

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode*greathead=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode*greattail=greathead;
        struct ListNode*lesshead=(struct ListNode*)malloc(sizeof(struct ListNode));
         struct ListNode*lesstail=lesshead;
         struct ListNode*cur=pHead;
         while(cur)
         {
            if(cur->val>=x)
            {
                greattail->next=cur;
                greattail=greattail->next;
                cur=cur->next;
            }
            else
            {
                lesstail->next=cur;
                lesstail=lesstail->next;
                cur=cur->next;
            }
         }
         //防止变成循环链表
         greattail->next=NULL;
         lesstail->next=greathead->next;
         
          struct ListNode*next=lesshead->next;
          free(greathead);
          free(lesshead);
          return next;
    }
};

这道题难在我们如何将链表链接,其实如大家画画图,把大的放一起,小的放一起,这样最后在链接他们就可以解决问题了。

第三题
判断链表是不是回文结构

在这里插入图片描述
这道题的思路真的很难想到,我们要先取出中间的位置,然后反转中间位置后面的链表,在进行比较,我们先把它当成数组来理解,就先找到中间数,然后反转后面的数,比如图中的1->2->2->1,经过我们上面的步骤就是变成1->2->1->2.然后从中间开始比较过去和第一个比较,如果相等的话就是回文到结束的时候。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

struct ListNode* midnode(struct ListNode* head)
{
        struct ListNode*slow,*fast;
        slow=fast=head;
        while(fast && fast->next )
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
}
struct ListNode*midreserve(struct ListNode*mid)
{
    struct ListNode*cur=mid;
    struct ListNode*prev=NULL;
    struct ListNode*head=mid;
    struct ListNode*next=mid->next;
    while(cur)
    {
        cur->next=prev;
        prev=cur;
        cur=next;
        if(next)
        {
            next=next->next;
        }
    }
    return prev;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode*mid=midnode(A);
        struct ListNode*remid=midreserve(mid);
        while(remid)
        {
            if(A->val!=remid->val)
            {
                return false;
            }
            A=A->next;
            remid=remid->next;

        }
        return true;
    }
};

这道题其实主要是思路难想到,又要先取这个链表的中点,然后再去倒置它,在按顺序进行比较,真的很难想到,想到了又很难去实现,首先我们先用快慢指针找到中点,然后将中间后面的数据进行逆置,可以用头插的方式,当然也可以用我们三个指针指向前后进行逆置。

做完这个我们再来一题分享题目就算是过去了,原因是后面的题目我也只是会一点,还要继续努力。

在这里插入图片描述
题目四
相交链表

在这里插入图片描述

在这里插入图片描述
这道题我们先用遍历一遍headA和headB算出他们的元素个数,然后找出长的,再找出长的时候我们就可以判断一个东西,那就是如果最后一个都不相同,那后面就不可能相同,所以结束的时候我们就可以先判断一下,然后让长链表先走k步,k是他们相差的数,然后我们就可以一起走,如果不相等就往后,一直到相等的时候,而且这是赢相等的,那我们来看一下代码吧!!

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
      struct ListNode *curA=headA;
      struct ListNode *curB=headB;
      int s1=1;
      int s2=1;
      while(curA->next)
      {
          curA=curA->next;
          s1++;
      }
      while(curB->next)
      {
          curB=curB->next;
          s2++;
      }
      if(curA!=curB)
      {
          return NULL;
      }
      int k=abs(s1-s2);
     struct ListNode *longNode=headA;
      struct ListNode *shortNode=headB;
      if(s1<s2)
      {
          longNode=headB;
          shortNode=headA;
      }
      while(k--)
      {
          longNode=longNode->next;
      }
      while(longNode!=shortNode)
      {
          longNode=longNode->next;
          shortNode=shortNode->next;
      }
      return shortNode;
}

今天的分享就到这里了,链表的题目后面还有,但是先不分享了等到后面再分享,下一期应该是双链表,这是一个很厉害的链表嗷!我们下次见