链表OJ题

今天继续分享我们关于链表的OJ题。
第一题

合并升序链表

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

那我们来写这道题吧。

structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}//如果链表一个为空，就直接返回不是空的链表。structListNode*head;structListNode*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;}

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

structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}structListNode*head=(structListNode*)malloc(sizeof(structListNode));
        head->next=NULL;structListNode* 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;}structListNode*next=head->next;free(head);return next;}

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

题目二
添加链接描述

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

class Partition {
public:
    ListNode*partition(ListNode* pHead,int x){// write code herestructListNode*greathead=(structListNode*)malloc(sizeof(structListNode));structListNode*greattail=greathead;structListNode*lesshead=(structListNode*)malloc(sizeof(structListNode));structListNode*lesstail=lesshead;structListNode*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;structListNode*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) {}
};*/structListNode*midnode(structListNode* head){structListNode*slow,*fast;
        slow=fast=head;while(fast && fast->next ){
            slow=slow->next;
            fast=fast->next->next;}return slow;}structListNode*midreserve(structListNode*mid){structListNode*cur=mid;structListNode*prev=NULL;structListNode*head=mid;structListNode*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 herestructListNode*mid=midnode(A);structListNode*remid=midreserve(mid);while(remid){if(A->val!=remid->val){return false;}
            A=A->next;
            remid=remid->next;}return true;}};

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

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

题目四
相交链表

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

structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){structListNode*curA=headA;structListNode*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){returnNULL;}int k=abs(s1-s2);structListNode*longNode=headA;structListNode*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;}

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