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
Solution1：recursive遞歸 寫(xiě)法
從起始每k個(gè)作為一段荤堪，實(shí)現(xiàn)reverse當(dāng)前段篱竭，并遞歸完成下一段的reverse希太。
Time Complexity: O(N) Space Complexity: O(k) 遞歸緩存
Solution2_a：iterative 寫(xiě)法: 依次reverse
依次reverse: 1 -> 2 -> 3 -> 4
1 <- 2 -> 3 -> 4 再 1 <- 2 -< 3 -> 4 再 1 <- 2 <- 3 <- 4
本題中將每一段(k個(gè)) 內(nèi)部依次reverse( 普通prev寫(xiě)法)狗唉，重新連接首尾后跳仿，繼續(xù)下一段
Time Complexity: O(N) Space Complexity: O(1)
Solution2_b：iterative 寫(xiě)法: (后部)插入法reverse
1 -> 2 -> 3 -> 4
2 -> 3 -> 4 -> 1 再 3 -> 4 -> 2 -> 1 再 4 -> 3 -> 2 -> 1
本題中將每一段(k個(gè)) 內(nèi)部依次插入法reverse志于，重新連接首尾后蛉签，繼續(xù)下一段
Time Complexity: O(N) Space Complexity: O(1)
Solution2_c：Iterative (前部)插入法reverse ?
1 -> 2 -> 3 -> 4
2 -> 1 -> 3 -> 4 再 3 -> 2 -> 1 -> 4 再 4 -> 3 -> 2 -> 1
Solution1 Code：
class Solution1 {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) { // find the k+1 node
curr = curr.next;
count++;
}
if (count == k) { // if k+1 node is found
curr = reverseKGroup(curr, k); // reverse next section
//reverse this section
while (count-- > 0) { // reverse current k-group:
ListNode tmp = head.next; // save head.next
head.next = curr; // (main) head.next = prev_head (except for the first time)
curr = head; // curr as prev_head
head = tmp; // head to original next
}
head = curr;
}
return head;
}
}
Solution2_a Code：
class Solution2_a {
/**
* Reverse a link list between begin and end exclusively
* an example:
* a linked list:
* 0->1->2->3->4->5->6
* | |
* begin end
* after call begin = reverse(begin, end)
*
* 0->3->2->1->4->5->6
* | |
* begin end
* @return the reversed list's 'begin' node, which is the precedence of node end
*/
public ListNode reverseKGroup(ListNode head, int k) {
ListNode begin;
if (head == null || head.next == null || k == 1)
return head;
ListNode dummyhead = new ListNode(0);
dummyhead.next = head;
begin = dummyhead;
int i=0;
while (head != null){
i++;
if (i % k == 0){
begin = reverse(begin, head.next);
head = begin.next;
} else {
head = head.next;
}
}
return dummyhead.next;
}
public ListNode reverse(ListNode begin, ListNode end) {
ListNode curr = begin.next;
ListNode next, first;
ListNode prev = begin;
first = curr;
while (curr != end){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
begin.next = prev;
first.next = curr;
return first;
}
}
Solution2_b Code：
lass Solution2_b {
public ListNode reverseKGroup(ListNode head, int k) {
if (head==null||head.next==null||k<2) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode tail = dummy, prev = dummy,temp;
int count;
while(true) {
count = k;
while(count > 0 && tail != null){
count--;
tail = tail.next;
}
if(tail == null) break;//Has reached the end
head = prev.next;//for next cycle
// prev-->temp-->...--->....--->tail-->....
// Delete @temp and insert to the next position of @tail
// prev-->...-->...-->tail-->head-->...
// Assign @temp to the next node of @prev
// prev-->temp-->...-->tail-->...-->...
// Keep doing until @tail is the next node of @prev
while(prev.next != tail){
temp = prev.next;//Assign
prev.next = temp.next;//Delete
temp.next = tail.next;
tail.next = temp;//Insert
}
tail = head;
prev = head;
}
return dummy.next;
}
}
