25. 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.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is:
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
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list's nodes, only nodes itself may be changed.
Solution
(1) Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode next = null;
ListNode p1 = head;
while (p1 != null) {
for (int i = 1; i < k; i++) {
p1 = p1.next;
if (p1 == null) {
return dummy.next;
}
}
next = p1.next;
p1 = prev.next;
ListNode p2 = p1.next;
while(p2 != null && p2 != next) {
ListNode p3 = p2.next;
p2.next = p1;
p1 = p2;
p2 = p3;
}
ListNode p0 = prev.next;
p0.next = next;
prev.next = p1;
prev = p0;
p1 = next;
}
return dummy.next;
}
}
(2) 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 not head:
return head
node = head
for _ in xrange(1, k):
node = node.next
if not node:
return head
next = self.reverseKGroup(node.next, k)
for _ in xrange(0, k):
p1 = head.next
head.next, next, head = next, head, p1
return next
(3) Scala
Recursive
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
object Solution {
def reverseKGroup(head: ListNode, k: Int): ListNode = {
if (head == null) {
return head
}
var node = head
for (i <- 1 until k) {
node = node.next
if (node == null) {
return head
}
}
var prev = reverseKGroup(node.next, k)
var hdr = head
for (i <- 0 until k) {
val next = hdr.next
hdr.next = prev
prev = hdr
hdr = next
}
return prev
}
}
Iterative
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
object Solution {
def reverseKGroup(head: ListNode, k: Int): ListNode = {
val dummy: ListNode = ListNode(0)
dummy.next = head
var prev: ListNode = dummy
var p0 = head
while (true) {
var next = p0
for (i <- 1 until k) {
if (next == null) {
return dummy.next
}
next = next.next
}
if (next == null) {
return dummy.next
}
next = next.next;
for (i <- 0 until k) {
var p1 = p0.next
p0.next = next
next = p0
p0 = p1
}
val p2 = prev.next
prev.next = next
prev = p2
}
return dummy.next
}
}