LeetCode 25. Reverse Nodes in k-Group

Problem:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int count = countNodes(head);
        int num = count - count % k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        int done = 0;
        while(done < num) {
            ListNode run = current;
            for (int i = 0; i <= k; i++)
                run = run.next;
            current.next = reverseK(current.next, k);
            for (int i = 0; i < k; i++)
                current = current.next;
            current.next = run;
            done += k;
        }
        return dummy.next;
    }
    
    private int countNodes(ListNode head) {
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
    
    private ListNode reverseK(ListNode current, int k) {
        if (k == 1) {
            return current;
        }
        ListNode tail = current.next;
        ListNode head = reverseK(current.next, k - 1);
        tail.next = current;
        return head;
    }
}

6 thoughts on “LeetCode 25. Reverse Nodes in k-Group”

  1. FineScan 會在肌膚上製造數以千計的細小深入傷口,即所謂的顯微加熱區(microthermal zone),但要確保每次治療時皆有部份組織不受能量影響,於是,每一個顯微加熱區的作用雖然強烈而明顯,但周圍都包覆著正常且結構完整的皮膚組織,使傷口能在短時間內癒合,並替換之前有缺陷的受損組織。Finescan不僅可讓表皮新生,更可促進深層膠原再生,從內而外徹底喚醒細胞,瞬時找回年輕時的肌膚狀態。憑藉最新的雙軸技術,FINESCAN 6可治療 – 面部 – 頸部 – 暗瘡凹凸洞 – 增生性疤痕

  2. Venus Legacy™是第一個,也是唯一一個得到美國食品藥品監督管理局批准,利用4D™技術結合多極射頻(RF)、磁力脈衝、變量脈衝VariPulse™技術(VP)和實時熱力反饋的設備,這使Venus Legacy™能夠提供一個既安全又無痛的療程,並取得理想效果。Venus Legacy™的療程為所有類型的肌膚提供一個100安全和無痛的美容過程,並針對面部、頸部及身體各處,提供以下即時和持久的效果 非手術塑型 減少橙皮紋 減少皺紋 減少皮下脂肪 收緊肌膚

Leave a Reply

Your email address will not be published. Required fields are marked *