25.Reverse-Nodes-in-k-Group

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.

代码

Approach #1 Recursive

Time: O(n) Space: O(n/k)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseLinkedList(ListNode head, int k) {
// Reverse k nodes of the given linked list.
// This function assumes that the list contains
// atleast k nodes.
ListNode new_head = null;
ListNode cur = head;
while (k > 0) {
// Keep track of the next node to process in the
// original list
ListNode next = cur.next;
// Insert the node pointed to by "ptr"
// at the beginning of the reversed list
cur.next = new_head;
new_head = cur;
// Move on to the next node
cur = next;
// Decrement the count of nodes to be reversed by 1
k--;
}
// Return the head of the reversed list
return new_head;
}
public ListNode reverseKGroup(ListNode head, int k) {
int count = 0;
ListNode ptr = head;
// First, see if there are atleast k nodes
// left in the linked list.
while (count < k && ptr != null) {
ptr = ptr.next;
count++;
}
// If we have k nodes, then we reverse them
if (count == k) {
// Reverse the first k nodes of the list and
// get the reversed list's head.
ListNode reversedHead = this.reverseLinkedList(head, k);
// Now recurse on the remaining linked list. Since
// our recursion returns the head of the overall processed
// list, we use that and the "original" head of the "k" nodes
// to re-wire the connections.
head.next = this.reverseKGroup(ptr, k);
return reversedHead;
}
return head;
}
}

Approach #2 Iterative

public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pointer = dummy;
while (pointer != null) {
ListNode node = pointer;
// first check whether there are k nodes to reverse
for (int i = 0; i < k && node != null; i++) {
node = node.next;
}
if (node == null) break;
// now we know that we have k nodes, we will start from the first node
ListNode prev = null, curr = pointer.next, next = null;
for (int i = 0; i < k; i++) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
ListNode tail = pointer.next;
tail.next = curr;
pointer.next = prev;
pointer = tail;
}
return dummy.next;
}