今天继续分享我们关于链表的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; }
今天的分享就到这里了，链表的题目后面还有，但是先不分享了等到后面再分享，下一期应该是双链表，这是一个很厉害的链表嗷！我们下次见
