Thursday, July 24, 2014

Reverse Nodes in k-Group

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

计算一共要反转多少个group,对每个gruop在反转k-1次。
public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        
        int length = getLength(head);
        int num = length / k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        int i = 0;
        while (i < num) {
            int j = 0;
            while (j < k - 1) {
                ListNode tmp = head.next;
                head.next = tmp.next;
                tmp.next = pre.next;
                pre.next = tmp;
                j++;
            }
            pre = head;
            head = pre.next;
            i++;
        }
        return dummy.next;
    }
    
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}

No comments:

Post a Comment