Java&Go-LeetCode25. K 个一组翻转链表-递归

• 算法
  • 1.找到前K个节点范围，当不足K个时返回head
  • 2.记录接下来K个的开头
  • 3.翻转前K个节点
  • 4.用刚才记录的接下来K个节点的开头递归翻转后面的，然后连接到前K个翻转前的head节点
  • ps：2和3顺序不能反过来，因为翻转后会改变原链表的指向

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || k == 1) {
        return head;
    }

    ListNode right = head;
    for (int i = 1; i < k; i++) {
        right = right.next;
        if (right == null) {
            return head;
        }
    }
    ListNode next = right.next;
    reverseRange(head, next);
    head.next = reverseKGroup(next, k);
    return right;
}

private ListNode reverseRange(ListNode left, ListNode boundary) {
    ListNode prev = null;
    ListNode curr = left;
    while (curr != boundary) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || k == 1 {
        return head
    }

    right := head
    for i := 1; i < k; i++ {
        right = right.Next
        if right == nil {
            return head
        }
    }

    next := right.Next
    reverseRange(head, next)
    head.Next = reverseKGroup(next, k)
    return right
}

func reverseRange(left, right *ListNode) *ListNode {
    var prev, curr *ListNode = nil, left
    for curr != right {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}