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.
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
Leetcode link
Lintcode link
Solution:
Go through the list to obtain the length of the list.
Reverse the successive k nodes if the lenght of the right side is greater than k.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
> File Name: ReverseNodesinK-Group.java
> Author: Yao Zhang
> Mail: psyyz10@163.com
> Created Time: Wed 18 Nov 23:51:11 2015
************************************************************************/
public class ReverseNodesinK-Group{
public ListNode reverseKGroup(ListNode head, int k) {
if (k == 0 || k == 1)
return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
int length = 0;
while (head != null){
length++;
head = head.next;
}
head = dummy;
while (length >= k){
head = reverse(head, k);
length -= k;
}
return dummy.next;
}
public ListNode reverse(ListNode node, int k){
ListNode head = node.next;
ListNode startNode = head;
ListNode prev = null;
for (int i = 0; i < k ; i++){
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
startNode.next = head;
node.next = prev;
return startNode;
}
}
|