题解
理解了思路就根据分析的内容进行编写代码：
1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 2. { 3. if(list1==NULL) //考虑原链表中有空链表的情况。 4. return list2; 5. if(list2==NULL) 6. return list1; 7. struct ListNode* head=NULL,*tail=NULL; 8. while(list1&&list2) 9. { 10. if(list1->val > list2->val)//比较大小取小的尾插 11. { 12. if(head==NULL) //考虑特殊情况新建链表为NULL时进行特殊处理 13. { 14. tail=head=list2; 15. 16. } 17. else //尾插 18. { 19. tail->next=list2; 20. tail=tail->next; 21. } 22. list2=list2->next; //尾插后继续向后 23. } 24. else 25. { 26. if(head==NULL) 27. { 28. tail=head=list1; 29. 30. } 31. else 32. { 33. tail->next=list1; 34. tail=tail->next; 35. } 36. 37. list1=list1->next; 38. } 39. } 40. if(list2==NULL) //一个链表为NULL时将另一个链表剩余的节点尾插到新链表。 41. tail->next=list1; 42. else 43. tail->next=list2; 44. return head; 45. }
虽然思路非常简单，但是代码实现却很不容易，需要很多要考虑的特殊情况。
方法二
和思路一相同，也是比较大小，将小的尾插到新的链表。但是可以使用带头结点的链表，这样再插入时就不需要考虑新链表为NULL时的情况，进行特殊处理。可以更好的简化代码。
题解
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) return list2; if(list2==NULL) return list1; struct ListNode* head=NULL,*tail=NULL; head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); 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(list2==NULL) tail->next=list1; else tail->next=list2; struct ListNode* del=head; head=head->next; free(del); return head; }
注意：原链表中不带头节点，返回时不能返回头节点，需要将头节点释放掉，返回头节点的下一个节点。
题目四：链表的回文结构
题目描述：
题目链接：
思路
有人可能会想，这不很简单吗？把这个链表反转一下，再和原链表数据依次比较不就解决了，但是这里注意题目要求。
题目要求时间复杂度为O(N)，空间复杂度为O(1)，上述思路需要将原链表复制一份后才可以与逆置是链表进行比较，空间复杂度为O(N)。
这道题的思路是这样的，可以先找到链表的中间节点，然后从中间节点开始，对后部分的链表进行逆置，然后从中间开始与开头的节点对比，看两个值是否相同。
分析
情况一：
节点为偶数个，把后半部分节点逆置，然后依次比较，这里注意其实前半部分的2节点的next这时依然指向的是后半部分的2，后半部分的2节点的next指向NULL。如下图：
逆置之后，返回的是后半部分1节点的地址，然后进行遍历，直到为NULL结束。
情况二：
节点数量为奇数个
实际情况和上述一样：
但这里在比较的时候就要注意一下3节点，这里不需要把前半部分2节点的next置为NULL，当遍历到最后时，都遍历到了3节点一定是相同的
题解
当然这些逆置、找中间节点的接口我们已经写过了，可以CV一下前边的代码，这样写代码还是很舒服的Ctrl+C、Ctrl+V
当然借此我再介绍一种新的逆置链表的方法，我们可以使用头插来实现链表逆置。将原链表的节点依次头插到新的节点，这样就轻松实现了逆置。
代码如下：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* newhead=NULL; while(cur) { struct ListNode* next=cur->next; //头插 cur->next=newhead; newhead=cur; cur=next; } return newhead; }
整体题解：
class PalindromeList { public: struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* newhead=NULL; while(cur) { struct ListNode* next=cur->next; cur->next=newhead; newhead=cur; cur=next; } return newhead; } struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast=head,*slow=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; } return slow; } bool chkPalindrome(ListNode* A) { struct ListNode* mid=middleNode(A);//中间节点 struct ListNode* rmid=reverseList(mid);//反转后的中间节点 while(A && rmid) { if(A->val!=rmid->val) { return false; } else { rmid=rmid->next; A=A->next; } } return true; } };
总结
好的本期内容到此结束，后续我将会分享更多数据结构相关的题目，通过画图逐步分析，来帮助大家刷题，这些题目建议大家先做一遍，然后看思路与分析，一定要动手敲一敲代码。最后，感谢阅读!
