@@ -0,0 +1,2440 @@
+/***%0A * Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.%0A *%0A * If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.%0A *%0A * You may not alter the values in the nodes, only nodes itself may be changed.%0A *%0A * Only constant memory is allowed.%0A *%0A * For example,%0A * Given this linked list: 1-%3E2-%3E3-%3E4-%3E5%0A *%0A * For k = 2, you should return: 2-%3E1-%3E4-%3E3-%3E5%0A *%0A * For k = 3, you should return: 3-%3E2-%3E1-%3E4-%3E5%0A */%0A%0A/**%0A * Definition for singly-linked list.%0A * public class ListNode %7B%0A *     int val;%0A *     ListNode next;%0A *     ListNode(int x) %7B%0A *         val = x;%0A *         next = null;%0A *     %7D%0A * %7D%0A */%0A%0Apublic class Solution %7B%0A    // Solution 1: Recursive O(n) O(1)%0A    /*%0A    public ListNode reverseKGroup(ListNode head, int k) %7B%0A        if (head == null %7C%7C head.next == null %7C%7C k %3C 2)%0A            return head;%0A%0A        ListNode next_group = head;%0A        for (int i = 0; i %3C k; i++) %7B%0A            if (next_group != null)%0A                next_group = next_group.next;%0A            else%0A                return head;%0A        %7D%0A%0A        ListNode new_next_group = reverseKGroup(next_group, k);%0A        ListNode prev = null;%0A        ListNode cur = head;%0A        while (cur != next_group) %7B%0A            ListNode next = cur.next;%0A            cur.next = prev != null ? prev : new_next_group;%0A            prev = cur;%0A            cur = next;%0A        %7D%0A        return prev;%0A    %7D%0A    */%0A    %0A    // Solution 2: Iterative O(n) O(1)%0A    public ListNode reverseKGroup(ListNode head, int k) %7B%0A        if (head == null %7C%7C head.next == null %7C%7C k %3C 2)%0A            return head;%0A        ListNode ret = new ListNode(0);%0A        ret.next = head;%0A%0A        for (ListNode prev = ret, end = head; end != null; end = prev.next) %7B%0A            for (int i = 1; i %3C k && end != null; i++)%0A                end = end.next;%0A            if (end == null) break;%0A            prev = reverse(prev, prev.next, end);%0A        %7D%0A        return ret.next;%0A    %7D%0A%0A    private ListNode reverse(ListNode prev, ListNode begin, ListNode end) %7B%0A        ListNode end_next = end.next;%0A        for (ListNode p = begin, cur = p.next, next = cur.next;%0A                cur != end_next;%0A                p = cur, cur = next,%0A                next = next != null ? next.next : null) %7B%0A            cur.next = p;%0A        %7D%0A        begin.next = end_next;%0A        prev.next = end;%0A        return begin;%0A    %7D%0A%0A%0A%7D%0A

add ReverseNodesink-Group.java