1. 相交链表
给你两个单链表的头节点 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 个节点。
示例 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 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
出处：
https://edu.csdn.net/practice/27308139
代码：
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) { return NULL; } ListNode *cur1 = headA; ListNode *cur2 = headB; while (cur1 != cur2) { cur1 = cur1 ? cur1->next : headB; cur2 = cur2 ? cur2->next : headA; } return cur1; } }; ListNode* buildNodeList(vector<int> vec) { ListNode *head = new ListNode(0); ListNode *p = head; for (size_t i = 0; i < vec.size(); i++) { ListNode *node = new ListNode(vec[i]); p->next = node; p = p->next; } return head->next; } void testIntersection(ListNode *headA, ListNode *headB, int skipA, int skipB){ ListNode *p = headA, *q = headB; for (int i = 0; i < skipA; i++) p = p->next; for (int i = 0; i < skipB; i++) q = q->next; if (p != NULL && q->next != NULL) q->next = p; Solution sol; ListNode *res = sol.getIntersectionNode(headA, headB); if (res != NULL) cout << "Intersected at: " << res->val << endl; else cout << "null" << endl; } int main() { vector<int> listA = {4,1,8,4,5}; vector<int> listB = {5,0,1,8,4,5}; int skipA = 2, skipB = 3; ListNode *headA = buildNodeList(listA); ListNode *headB = buildNodeList(listB); testIntersection(headA,headB,skipA, skipB); listA = {0,9,1,2,4}; listB = {3,2,4}; skipA = 3; skipB = 1; headA = buildNodeList(listA); headB = buildNodeList(listB); testIntersection(headA,headB,skipA, skipB); listA = {2,6,4}; listB = {1,5}; skipA = 3; skipB = 2; headA = buildNodeList(listA); headB = buildNodeList(listB); testIntersection(headA,headB,skipA, skipB); return 0; }
输出：
Intersected at: 8
Intersected at: 2
null
2. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5
出处：
https://edu.csdn.net/practice/27308141
代码：
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode *sortList(ListNode *head) { return mergesort(head); } ListNode *mergesort(ListNode *node) { if (!node || !node->next) return node; ListNode *fast = node; ListNode *slow = node; ListNode *brek = node; while (fast && fast->next) { fast = fast->next->next; brek = slow; slow = slow->next; } brek->next = nullptr; ListNode *l1 = mergesort(node); ListNode *l2 = mergesort(slow); return merge(l1, l2); } ListNode *merge(ListNode *l1, ListNode *l2) { if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; } if (l1->val < l2->val) { l1->next = merge(l1->next, l2); return l1; } else { l2->next = merge(l2->next, l1); return l2; } } }; ListNode* buildNodeList(vector<int> vec) { ListNode *head = new ListNode(0); ListNode *p = head; for (size_t i = 0; i < vec.size(); i++) { ListNode *node = new ListNode(vec[i]); p->next = node; p = p->next; } return head->next; } string NodeList2String(ListNode *head) { if (head==nullptr) return "[]"; ListNode *p = head; string res; while (p != nullptr) { res.append(to_string(p->val)); res.append("->"); p = p->next; } res.append("null"); return res; } int main() { Solution s; vector<int> nums = {4,2,1,3}; ListNode *head = buildNodeList(nums); cout << NodeList2String(head) << endl; head = s.sortList(head); cout << NodeList2String(head) << endl; nums = {-1,5,3,4,0}; head = buildNodeList(nums); cout << NodeList2String(head) << endl; head = s.sortList(head); cout << NodeList2String(head) << endl; return 0; }
输出：
4->2->1->3->null
1->2->3->4->null
-1->5->3->4->0->null
-1->0->3->4->5->null
3. 重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例 2:
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
提示：
链表的长度范围为 [1, 5 * 10^4]
1 <= node.val <= 1000
出处：
https://edu.csdn.net/practice/27729559
代码：
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: void reorderList(ListNode *head) { ListNode *l1 = head, *l2 = head; ListNode *tep = head; int len = 0; while (tep) { len++; tep = tep->next; } if (len <= 2) return; int len1 = len / 2 + len % 2; int len2 = len / 2; for (int i = 0; i < len1 - 1; i++) { head = head->next; } l2 = head->next; head->next = nullptr; head = l1; stack<ListNode *> stk; while (l2) { stk.push(l2); l2 = l2->next; } while (!stk.empty()) { tep = stk.top(); stk.pop(); tep->next = l1->next; l1->next = tep; l1 = tep->next; } } }; ListNode* buildNodeList(vector<int> vec) { ListNode *head = new ListNode(0); ListNode *p = head; for (size_t i = 0; i < vec.size(); i++) { ListNode *node = new ListNode(vec[i]); p->next = node; p = p->next; } return head->next; } string NodeList2String(ListNode *head) { if (head==nullptr) return "[]"; ListNode *p = head; string res; while (p != nullptr) { res.append(to_string(p->val)); res.append("->"); p = p->next; } res.append("null"); return res; } int main() { Solution s; vector<int> nums = {1,2,3,4}; ListNode *head = buildNodeList(nums); cout << NodeList2String(head) << endl; s.reorderList(head); cout << NodeList2String(head) << endl; nums = {1,2,3,4,5}; head = buildNodeList(nums); cout << NodeList2String(head) << endl; s.reorderList(head); cout << NodeList2String(head) << endl; return 0; }
输出：
1->2->3->4->null
1->4->2->3->null
1->2->3->4->5->null
1->5->2->4->3->null
