Reverse Nodes in k-Group
Problem: Reverse Nodes in k-Group
We can do this recursively. We find the first k nodes and trim it out and reverse it. Then we recursively deal with the remaining linked list and append the results.
Code in Python:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if k <= 1: return head
if not head: return None
node = head
for _ in xrange(k-1):
node = node.next
if not node: return head
second, node.next = node.next, None
prev, node = None, head
while node:
tmp = node.next
node.next, prev, node = prev, node, tmp
head.next = self.reverseKGroup(second, k)
return prev
Code in Java:
/**
* 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) {
ListNode node = head;
for (int i = 0; i < k; i++) {
if (node != null)
node = node.next;
else
return head;
}
List<ListNode> res = new ArrayList<ListNode>();
res = reverseGroup(head, k);
res.get(1).next = reverseKGroup(node, k);
return res.get(0);
}
private List<ListNode> reverseGroup(ListNode head, int k) {
ListNode prev = null;
ListNode node = head;
for (int i = 0; i < k; i++) {
ListNode tmp = node;
node = node.next;
tmp.next = prev;
prev = tmp;
}
List<ListNode> res = new ArrayList<ListNode>();
res.add(prev);
res.add(head);
return res;
}
}