链表OJ题

在这里插入图片描述
今天继续分享我们关于链表的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;
}