Reverse Nodes in k-Group

题意:给定一个链表和数字k,要求每k个节点翻转,返回链表头。如果链表长度不是k的倍数,剩余部分不做处理。

25. Reverse Nodes in k-Group (opens new window)

此题是上一题的扩展,要求每k个节点做翻转,问题可以分三步解决,把链表拆分为n个部分,对其做链表翻转,最后将其拼接起来。因为需要知道链表长度才能判断是否有剩余部分,所以多遍历了一遍链表。时间复杂度为O(2n),空间复杂度为O(1)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int size = 0;
        ListNode tmp = head;
        // 计算链表长度
        while (tmp != null) {
            size++;
            tmp = tmp.next;
        }
        // head前拼接一个节点,方便后续处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode left = null;
        ListNode right = null;
        // 计算需要翻转的部分
        for (int i = 0; i <= size - k; i += k) {
            left = prev.next;
            // 返回翻转后的head
            right = reverse(left, k);
            // 上一段拼接上right
            prev.next = right;
            // 重置prev
            prev = left;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head, int k) {
        // 翻转链表,把head.next指向tail.next,返回翻转后的head
        ListNode last = null;
        ListNode current = head;
        ListNode next = null;
        for (int i = 0; i < k; i++) {
            next = current.next;
            current.next = last;
            last = current;
            current = next;
        }
        head.next = next;
        return last;
    }
}