【题单】反转链表
链表题单 206. 反转链表 p1 指向前一个节点，p2 指向当前节点，p3 指向下一个节点。 每次只修改 p2 节点，使它指向 p1，然后向右移动 p1, p2，p3 的作用是记录下一个 p2 的位置。 当 p2 为空时，说明整个链表反转结束。记得把原链表头的 next 指针置为空。 ListNode *reverseList(ListNode *head) { if (!head) return head; LNP p1 = head; LNP p2 = p1->next; LNP p3{NULL}; while (p2) { p3 = p2->next; p2->next = p1; p1 = p2; p2 = p3; } head->next = NULL; return p1; } 92. 反转链表 II 这道题目使用一次遍历看起来复杂，其实只要观察到边界条件，其实是不难，多使用几个变量保存需要保存的信息更清晰。 首先我们需要找到要反转区间的前一个位置 st，然后找到反转区间的起点和终点 q1, q2，然后找到反转区间的下一个节点 en。找到 st 需要从 ro 节点走 left - 1 步，找到 q2 节点需要从 ro 节点走 r 步。这两步可以使用一次遍历得到。接下来就是常规的反转链表。 ListNode *reverseBetween(ListNode *head, int left, int right) { LNP ro{new LN(0, head)}; LNP p1{ro}; int cnt{}; while (cnt < left - 1) { cnt++; p1 = p1->next; } LNP st = p1; LNP q1{st->next}; LNP p2{p1->next}; LNP p3{}; while (cnt < right) { p3 = p2->next; p2->next = p1; p1 = p2; p2 = p3; cnt++; } LNP q2{p1}; LNP en{p2}; st->next = q2; q1->next = en; LNP res = ro->next; delete ro; return res; } 24. 两两交换链表中的节点 这道题和反转一个区间内的链表类似，只不过区间长度是 2。 ...