【Check 42】2024-04-02 - 25. K 个一组翻转链表

[larscheng]

25. K 个一组翻转链表

[larscheng]

思路

• 迭代，统计总节点数，将节点分k个一组进行迭代，对单个组进行反转
• 反转时记录尾节点，用于连接下一组反转后的链表
• 最后将没有参与分组反转的节点连在尾部

  代码

class Solution {

//O(n)/O(1)
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode cur = head;
    int length = 0;
    while (cur!=null){
        cur = cur.next;
        length++;
    }
    ListNode dummy = new ListNode(0);
    ListNode temp  = dummy;
    cur = head;
    for (int i = 0; i+k <= length ; i+=k) {
        ListNode pre = null;
        ListNode tail = null;
        for (int j = 0; j < k; j++) {
            if (j==0){
                tail = cur;
            }
            //保留原始结构
            ListNode next = cur.next;
            //反转指向
            cur.next = pre;
            //继续遍历
            pre = cur;
            cur = next;

        }
        temp.next = pre;
        temp = tail ;
    }
    if (cur!=null){
        temp.next = cur;
    }
    return dummy.next;
}

}

### 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)