1.翻转链表

三指针 pre cur nxt

  1. ListNode reverse(ListNode head,ListNode tail) {
  2.     ListNode pre, cur, nxt;
  3.     pre = null; cur = head; nxt = head;
  4.     while (cur != tail) {
  5.         nxt = cur.next;
  6.         // 逐个结点反转
  7.         cur.next = pre;
  8.         // 更新指针位置
  9.         pre = cur;
  10.         cur = nxt;
  11.     }
  12.     // 返回反转后的头结点
  13.     return pre;
  14. }

2.k个一组递归

递归 + 长度判断 + 左闭右开

  1. a指向原head，k个一组翻转后变为tail
  2. b指向tail的下一个节点，也是下一组的head节点
  3. 链表剩余长度不足k时，不需要翻转，直接返回原head。

image.png

  1. ListNode reverseKGroup(ListNode head, int k) {
  2.     if (head == null) return null;
  3.     // 区间 [a, b) 包含 k 个待反转元素
  4.     ListNode a, b;
  5.     a = b = head;
  6.     for (int i = 0; i < k; i++) {
  7.         // 不足 k 个，不需要反转，base case
  8.         if (b == null) return head;
  9.         b = b.next;
  10.     }
  11.     // 反转前 k 个元素
  12.     ListNode newHead = reverse(a, b);
  13.     // 递归反转后续链表并连接起来
  14.     a.next = reverseKGroup(b, k);
  15.     return newHead;
  16. }