My O(N) time O(1) solution. Better Ideas?

• ``````public ListNode reverseKGroup(ListNode head, int k) {
if (head == null)
return null;

ListNode prevHead=null, prevTail=null;
ListNode cur=head, curHead = null;

int c = 0;
while(cur != null){
++c;
ListNode next = cur.next;
if (curHead == null){
curHead = cur;
c=1;
}

if (c == k){
// Within each group, do a normal reverse
reverse(curHead, cur);

// Link group with previous group
if (prevHead== null){
prevHead = cur;
}
if (prevTail!=null){
prevTail.next = cur;
}
prevTail=curHead;

// Reset group count
curHead = null;
}

cur = next;
}

if (prevTail!=null){
prevTail.next = curHead;
}

return prevHead == null? head:prevHead;
}

/**
* Normal reverse, head and tail will be switched after return
*/
public void reverse(ListNode head, ListNode tail){
if (head == tail)
return;

ListNode prev=null, cur=head, next=head.next;
while(!cur.equals(tail)){
cur.next = prev;
prev = cur;
cur = next;
next = cur.next;
}

cur.next = prev;
}``````

• Actually, the list is visited twice. A better solution only visit the list once. Refer to http://www.cnblogs.com/TenosDoIt/p/3794505.html

• This solution also visited nodes twice

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.