链表的回文结构
回文节后是对称的，所以这个题目我们可以先找到中间节点，然后将中间反转，然后两个指针，一个从头开始，一个从反转后的头节点开始，一一比对，如果val不相等一定不是回文，如果相等，那么一定是回文链表。
偶数个数据时
奇数个数据时：
所以我们可以清楚的知道当rmid为空时就要结束循环。
代码如下：
// 计算中间节点 struct ListNode* midNode(struct ListNode* head) { struct ListNode* fast = head,*slow = head; while(fast&&fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } // 翻转链表 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head, *newhead = NULL,*next = NULL; while(cur) { next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; } bool isPalindrome(struct ListNode* head) { //计算中间节点 struct ListNode* mid = midNode(head); //反转链表 struct ListNode* rmid =reverseList(mid); while(rmid) { //不相等一定不回文，返回false if(head->val!=rmid->val) { return false; } head = head->next; rmid = rmid->next; } //循环结束一定是回文 return true; }
链表分割
这个题我们需要两个链表，然后遍历原链表，将小于x的尾插到head1，将大于等于x的尾插带head2，然后将两个链表链接一下，需要注意的是我们需要将head2的为尾节点的next置空，不然可能会出现带环链表，还有就是我们的head1有可能为空，这里我们使用带哨兵位的链表，就可以解决这个问题，但是head2也可能为空，这时我们就需要将head1的尾节点next置空，不然就会存在非法访问。
代码如下：
struct ListNode* partition(struct ListNode* head, int x) { struct ListNode* head1,*tail1,*head2,*tail2; //开辟两个哨兵位 head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode)); head2 = tail2 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = head; while(cur) { if(cur->val<x) { //小于的尾插到tail1 tail1->next = cur; cur = cur->next; tail1 = tail1->next; } else { //大于的尾插到tail2 tail2->next = cur; cur = cur->next; tail2 = tail2->next; } } //链接两个链表 tail1->next = head2->next; //防止出现带环链表 tail2->next = NULL; if (head2->next == NULL) { //第二个链表为空，这是要将这是要将tail1->next置空，不然会出现非法访问 tail1->next = NULL; struct ListNode* next = head1->next; free(head2); free(head1); return next; } //保存头结点 struct ListNode* next = head1->next; //释放哨兵位 free(head1); free(head2); return next; }
两个链表的交集
判断是否相交非常简单，我们只需要判断两个链表的为节点是否相同就可以了，如果相同，那么它们一定是相交的，我们就可以找相加的那个节点，我们在找尾的时候可以记录一下两个链表的长度，由于从相交的位置开始后面的节点都一样了，我们可以计算出长的那个链表比短的链表长多少，让长的链表先走多少步，然后让两个链表同时走，相等的第一个节点就是我们要求的。
代码如下：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA,*curB = headB; int s1 = 1; int s2 = 1; //找A链表的尾，顺表记录长度 while(curA->next) { curA= curA->next; s1++; } //找B链表的尾，顺表记录长度 while(curB->next) { curB= curB->next; s2++; } //尾节点不相等一定不相交 if(curA!=curB) { return NULL; } //计算差值 int k = abs(s1-s2); //假设长的链表为A struct ListNode* longNode = headA,*shortNode = headB; //如果B链表长，则将长链表赋值B if(s1<s2) { longNode = headB; shortNode = headA; } //长链表先走k步 while(k--) { longNode= longNode->next; } //寻找第一个相等的节点 while(longNode!=shortNode) { longNode = longNode->next; shortNode = shortNode->next; } return longNode; }
链表循环
我们可以用快慢指针来解决这个问题，我们让慢指针走一步，快指针走两步，如果有环，那么当俩个指针都进入环中是，就是追击问题，如果快指针走到NULL，或者快指针的next为空，那么就意味着链表无环。
代码如下：
bool hasCycle(struct ListNode *head) { struct ListNode* fast = head,*slow = head; while(fast&&fast->next) { fast = fast->next->next; slow = slow->next; if(fast==slow) return true; } return false; }
思考
1.如果slow走一步，fast走二步是不是一定可以追上？
答案是一定可以追上，为什么呢，假设slow进环时fast与它相距N步，那么每走一步，他们之间的距离减少一，而N一定小于一圈的长度，所以在一圈之内fast一定追上slow。
2.如果slow走一步，fast走三步是不是一定可以追上？
答案是不太一定，假设他们之间的距离还是N，如果N是偶数那么就追上了，如果N奇数，他们就会错过，假设圆的长度为C，他们的距离就会变成C-1，这是又要分情况了，假设C-1位奇数那么就一定追不上了，如果C-1位偶数那么在下一圈的追击中就会追上。
链表周期 II
方法一
我们需要推导一个公式，假设头到入环点的长度为L，然后假设他们在环中相遇的点为X，入环点到X的距离为N，然后整个环的长度为C，我们可以推导：
有了这个推导关系我们就可以写代码了。
代码如下：
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head,*fast = head; while(fast&&fast->next) { fast = fast->next->next; slow = slow->next; //判断是否相遇 if(fast==slow) { struct ListNode* meet = fast,*cur = head; //一个从相遇点开始走，一个从头开始走 while(meet!=cur) { meet = meet->next; cur = cur->next; } //此时相遇的点就是入环点 return meet; } } //出循环一定没有环 return NULL; }
方法二
我们还是找相遇点，然后我们把相遇点的next置空，保存相遇点的next，然后就变成了相交链表。
代码如下：
//找相交链表的第一个相交点 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA,*curB = headB; int s1 = 1; int s2 = 1; //找A链表的尾，顺表记录长度 while(curA->next) { curA= curA->next; s1++; } //找B链表的尾，顺表记录长度 while(curB->next) { curB= curB->next; s2++; } //尾节点不相等一定不相交 if(curA!=curB) { return NULL; } //计算差值 int k = abs(s1-s2); //假设长的链表为A struct ListNode* longNode = headA,*shortNode = headB; //如果B链表长，则将长链表赋值B if(s1<s2) { longNode = headB; shortNode = headA; } //长链表先走k步 while(k--) { longNode= longNode->next; } //寻找第一个相等的节点 while(longNode!=shortNode) { longNode = longNode->next; shortNode = shortNode->next; } return longNode; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head,*fast = head; while(fast&&fast->next) { fast = fast->next->next; slow = slow->next; //判断是否相遇 if(fast==slow) { struct ListNode* meet = fast,*newhead = fast->next; //转换相交链表 meet->next = NULL; //找第一个相交点，也就是入环点 return getIntersectionNode(head,newhead); } } //出循环一定没有环 return NULL; }
总结一下：
方法一逻辑强，不好推导，但是推导出来代码好写
方法二逻辑没有那么强，适合我们普通人，但是代码量稍微大一点。
今天的分享就到这里结束了，感谢大家的关注和支持。
