链表
// 单链表节点的结构
1 | public class ListNode { |
链表反转
递归反转链表的一部分
1. 递归反转整个链表
明确递归函数的定义： 输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
1 | ListNode reverse(ListNode head) { |
2. 反转链表前N个节点
1 | // 将链表的前 n 个节点反转（n <= 链表长度） |
3. 反转链表的一部分
1 | ListNode reverseBetween(ListNode head, int m, int n) { |
25.k个一组反转链表
// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
while (cur != null) {
nxt = cur.next;
// 逐个节点反转
cur.next = pre;
// 更新指针位置
pre = cur; // 最后的值为最后的节点
cur = nxt; // 最后的值为NULL
}
// 返回反转后的头节点
return pre;
}
/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null; cur = a, nxt = a;
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
1 | ---------------- |
ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = b = head;
for (int i = 0 ; i < k ; i++) {
// 不足k个， 不需要反转， base case
if (b == null)
return head;
b = b.next;
}
// 反转前k个元素
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b, k);
return newHead;
}