Leetcode 25 Reverse Nodes in k-Group

Leetcode 25 Reverse Nodes in k-Group Edit Reverse Nodes in k-Group on GitHub

The problem description is as follow:

```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,

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

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

This problem seems difficult, but it will be much easier if we split the problem into small pieces.

Let’s take a look at the following singly linked list, we are trying to reverse nodes between `ListNode Pre` to `ListNode End`. Since we are trying to reverse linked list between `ListNode Pre` to `ListNode End``ListNode Last = Pre.next` will always be the last node of the reversed linked list.

```public ListNode reverse(ListNode pre, ListNode end){

ListNode last=pre.next;
ListNode cur=last.next;

while (cur!=end){

last.next=cur.next;
cur.next=pre.next;
pre.next=cur;

cur=last.next;
}
return last;
}```

The code above is trying to reverse linked list between `Pre` and `Cur`, and we could then reverse the whole linked list by moving `Cur` to `Cur.next`.  Reverse Nodes in k-Group

After previous analysis, this problem is simple. For a singly linked list, we create a Dummy ListNode and point to it’s head. Then we use previous algorithm to reverse nodes in k-group:

```/**
* Reverse a link list between pre and next exclusively
* 0->1->2->3->4->5->6
* |           |
* pre        next
* after call pre = reverse(pre, next)
*
* 0->3->2->1->4->5->6
*          |  |
*          pre next
*/```
```public ListNode reverseKGroup(ListNode head, int k) {
}

ListNode dummy =new ListNode (0);

ListNode pre=dummy;

int i=0;
while (cur!=null){
i++;
if (i%k==0){
pre=reverse(pre,cur.next);
cur=pre.next;
}
else {
cur=cur.next;
}
}
return dummy.next;
}```

Since we are traversing the singly linked list at most twice, the time complexity is `O(n)`.