Leetcode -234.回文链表
题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1, 2, 2, 1]
输出：true
示例 2：
输入：head = [1, 2]
输出：false
提示：
链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9
我们的思路是，把链表分为两个部分，以中间的结点为分界线，分为前半部分和后半部分，如果有两个中间结点，以第一个中间结点为标准；以1->2->2->1->NULL为例，如图：
然后反转以mid为中间结点的后半部分的链表，即反转以mid->next为头的链表；如下图：
反转完成的链表：
注意反转过程中改变了链表的结构，应该在返回前把反转的部分反转回来；下面看代码以及注释：
//找到链表前半部分的函数 struct ListNode* SLFindMid(struct ListNode* head) { struct ListNode* slow = head, * fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } return slow; } //反转链表的函数 struct ListNode* SLReverse(struct ListNode* head) { struct ListNode* curr = head, * prev = NULL; while (curr) { struct ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } bool isPalindrome(struct ListNode* head) { //通过SLFindMid函数找到链表的前半部分，返回的是前半部分的尾指针 //SLReverse函数反转后半部分的链表 struct ListNode* mid = SLFindMid(head); struct ListNode* reverse = SLReverse(mid->next); //p1从头开始，p2从反转后后半部分链表的头开始 struct ListNode* p1 = head; struct ListNode* p2 = reverse; //p1和p2通过迭代比较，当p2不为空则继续比较，p2为空说明前半部分和后半部分比较完了 while (p2) { if (p1->val == p2->val) { p1 = p1->next; p2 = p2->next; } //如果比较途中遇到不相等，返回false else { //把反转的后半部分反转回来，保持链表为原来的结构 SLReverse(reverse); return false; } } //最后把反转的后半部分反转回来，保持链表为原来的结构 SLReverse(reverse); return true; }
Leetcode -160.相交链表
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
如果两个链表不存在相交节点，返回 null 。
我们的思路是，分别计算两个链表的长度，再计算它们的差值gap，然后让长的那一个链表先走gap步，使它们从长度相同的结点出发比较；
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { //从头遍历两个链表，计算它们的长度 struct ListNode* tailA = headA, * tailB = headB; int lenA = 0, lenB = 0; while (tailA) { lenA++; tailA = tailA->next; } while (tailB) { lenB++; tailB = tailB->next; } //gap计算它们的差值，abs为取绝对值 int gap = abs(lenA - lenB); //假设A链表为长的那一个链表，B为短的链表 struct ListNode* longlist = headA, * shortlist = headB; //判断A和B谁是比较长的链表 if (lenA < lenB) { longlist = headB; shortlist = headA; } //让长的链表先走gap步 while (gap--) { longlist = longlist->next; } //两个链表从长度相同的结点出发比较 while (longlist != shortlist) { longlist = longlist->next; shortlist = shortlist->next; } return longlist; }
