6. 分割链表成两部分
面试题 02.04. 分割链表
难度中等
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
- 链表中节点的数目在范围 [0, 200] 内
- -100 <= Node.val <= 100
- -200 <= x <= 200
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* partition(struct ListNode* head, int x){ }
这题在牛客上标注较难，多了一个限制条件，且没有C语言提交的方式，但C++兼容C，用C++交就行
CM11 链表分割 链接：链表分割_牛客题霸_牛客网 (nowcoder.com)
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
哨兵位头结点+尾插代码:
struct ListNode* partition(struct ListNode* head, int x) { //开哨兵位头节点 方便尾插 struct ListNode* small_head = (struct ListNode*)malloc(sizeof(struct ListNode)); small_head->next = NULL; struct ListNode* large_head = (struct ListNode*)malloc(sizeof(struct ListNode)); large_head->next = NULL; struct ListNode* small_tail = small_head; struct ListNode* large_tail = large_head; while (head) { if (head->val < x) { small_tail->next = head; small_tail = small_tail->next; } else { large_tail->next = head; large_tail = large_tail->next; } head = head->next; } large_tail->next = NULL;//易忘记 可能成环 small_tail->next = large_head->next; struct ListNode* new_head = small_head->next; free(small_head);//临时指针可以不置空 free(large_head); return new_head; }
7. 链表的回文结构
234. 回文链表
（这两题是一模一样的）
难度简单
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；
否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围[1, 10^5] 内
- 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool isPalindrome(struct ListNode* head){ }
这题也在牛客上标注较难
OR36 链表的回文结构 链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
快慢指针+反转代码：
这题可以根据给的范围开出最大范围的数组，空间也是O（1）然后用数组判断回文，但不建议这么做
可以直接用前五道写过的找中间节点和反转函数的函数，但不熟还是要多写
画图发现如果不解链表的话也能找到终止条件
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newHead = NULL, * cur = head; while (cur) { struct ListNode* curNext = cur->next; cur->next = newHead;//头插 newHead = cur;//迭代往后走 cur = curNext; } return newHead; } struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast = head, * slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next;//快指针一次走两步 slow = slow->next;//慢指针一次走一步 } return slow; } bool isPalindrome(struct ListNode* head) { struct ListNode* mid = middleNode(head); struct ListNode* reverse_mid = reverseList(mid); while (head && reverse_mid) { if (head->val != reverse_mid->val) { return false; } else { head = head->next; reverse_mid = reverse_mid->next; } } return true; }
8. 找两个链表的第一个公共结点
160. 相交链表
（链接题目都是一样的，给这么多链接只是为了知道这题在很多地方出现）
难度简单
给你两个单链表的头节点 headA和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
- intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
- listA - 第一个链表
- listB - 第二个链表
- skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
- skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
- listA 中节点数目为 m
- listB 中节点数目为 n
- 1 <= m, n <= 3 * 104
- 1 <= Node.val <= 105
- 0 <= skipA <= m
- 0 <= skipB <= n
- 如果 listA 和 listB 没有交点，intersectVal 为 0
- 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { }
思路1 :暴力求解-穷举
依次取A链表中的每个节点跟B链表中的所有节点比较
如果有地址相同的节点，就是相交,返回第一个相同的交点
时间：O(N^2) 不符合题意
思路2: 时间要求优化到O(N)
1、尾节点相同就是相交，否则就不相交
2、求交点:长的链表先走(长度差)步,再同时走，返回第一个相同的交点
数据结构与算法⑥(第二章OJ题，下)后八道链表面试题（中）:https://developer.aliyun.com/article/1513365
