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.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For 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
给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。
Notes:
使用栈,当栈内的元素足够k个,弹出所有元素形成新的链表。不足k个元素时入栈。
注意测试数据:
[],1
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class ReverseNodes {
public ListNode reverseKGroup(ListNode head, int k) {
Stack<ListNode> stack = new Stack<>();
int index = 0;
ListNode result = null;
ListNode left = null;
ListNode right;
boolean isFirst = true;
while (head != null) {
right = head;
head = head.next;
right.next = null;
stack.push(right);
index++;
if (k == index) {
index = 0;
if (isFirst) {
result = revers(stack);
left = result;
isFirst = false;
} else {
left.next = revers(stack);
}
while (left.next != null) {
left = left.next;
}
}
}
while (!stack.empty()) {
if (left == null) {
result = stack.remove(0);
left = result;
} else {
left.next = stack.remove(0);
left = left.next;
}
}
return result;
}
private ListNode revers(Stack<ListNode> stack) {
ListNode head;
ListNode temp = stack.pop();
head = temp;
while (!stack.empty()) {
temp.next = stack.pop();
temp = temp.next;
}
return head;
}
}