Code More Create

Appearance

Return to top
On this page

25.K个一组翻转链表

题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？ 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路分析

将原问题拆解为更小的子问题进行解答

  • 将前k个结点进行反转
  • 对k+1到剩下结点，继续进行递归
  • 将两部分连接起来

AC 代码 

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // base case
        if(head == null) return null;
        ListNode oldHead = head,nextHead = head;
        // 遍历k次，找到递归的新头结点
        for(int i = 0; i < k; i++){
            // 如果剩余的不足k，直接返回原链表
            if(nextHead == null) return head;
            nextHead = nextHead.next;
        }
        // 将新旧结点之间的区域（左闭右开）进行反转，拿到反转后的头结点
        ListNode ans = reverse(oldHead,nextHead);
        // 此时旧头结点已经成为反转后的最后一个结点，对剩下部分继续递归，将两部分连接
        oldHead.next = reverseKGroup(nextHead,k);
        // 返回新头节点
        return ans;
    }
    // 反转区间为[head,tail)链表
    public ListNode reverse(ListNode head,ListNode tail){
        ListNode prev = head,cur = head.next,next = null;
        prev.next = null;
        while(cur != tail){
            // 保存当前结点的下一个结点
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}