重排链表


给定一个单链表 L:L0→L1→…→Ln-1→Ln , 将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1: ``` 给定链表 1->2->3->4, 重新排列为 1->4->2->3. ``` 示例 2: ``` 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3. ``` 解答: ``` ListNode* reorderList(ListNode* head) { if (!head) return head; ListNode* h = head; vector collection; while (h) { collection.push_back(h); h = h->next; } int size = collection.size(); int n = size / 2; for (int i = 0; i < n; i++) { int right = size - 1 - i; collection[i]->next = collection[right]; collection[right]->next = collection[i + 1]; if (i == n - 1 && size % 2 == 0) { collection[right]->next = nullptr; } if (i == n - 1 && size % 2 != 0) { collection[right]->next->next = nullptr; } } return head; } ```

k个一组翻转链表


给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。 示例 : ``` 给定这个链表:1->2->3->4->5 当 k = 2 时,应当返回: 2->1->4->3->5 当 k = 3 时,应当返回: 3->2->1->4->5 ``` 说明 : - 你的算法只能使用常数的额外空间。 - 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 ``` ListNode * reverseKGroup(ListNode* head, int k) { if (!head) return head; bool flag = true; ListNode* h = head; for (int i = 0; i < k; i++) { if (!h) { flag = false; break; } h = h->next; } if (!flag) return head; h = head; vector collection; for (int i = 0; i < k; i++) { collection.push_back(h); h = h->next; } for (int i = 0; i < k; i++) { if (i == 0) { collection[i]->next = reverseKGroup(h, k); } else { collection[i]->next = collection[i - 1]; } } return collection.back(); } ```

两两交换链表中的节点


给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 示例: ``` 给定 1->2->3->4, 你应该返回 2->1->4->3. ``` 说明: - 你的算法只能使用常数的额外空间。 - 你**不能只是单纯的改变节点内部的值**,而是需要实际的进行节点交换。 解答: ``` ListNode * swapPairs(ListNode* head) { if (!head || !head->next) return head; auto a = head; auto b = a->next; auto c = b->next; a->next = swapPairs(c); b->next = a; return b; } ```

有序链表转换二叉搜索树


给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 > 高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: ``` 给定的有序链表: [-10, -3, 0, 5, 9], 一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5 ```

回文链表


请检查一个链表是否为回文链表。 进阶: 你能在 O(n) 的时间复杂度和 O(1) 的复杂度中做到吗? 解答: ``` bool isPalindrome(ListNode* head) { vector collection; while (head) { collection.push_back(head->val); head = head->next; } for (auto i = collection.begin(), j = collection.end(); i < j; i++, j--) { if (*i != *(j - 1)) { return false; } } return true; } ```