Dada una lista enlazada, escriba una función para invertir cada k Node alternativo (donde k es una entrada a la función) de manera eficiente. Da la complejidad de tu algoritmo.
Ejemplo:
Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3 Output: 3->2->1->4->5->6->9->8->7->NULL.
Método 1 (procesar 2k Nodes y llamar recursivamente al resto de la lista):
este método es básicamente una extensión del método discutido en esta publicación.
kAltReverse(struct node *head, int k)
1) Reverse first k nodes.
2) In the modified list head points to the kth node. So change next
of head to (k+1)th node
3) Move the current pointer to skip next k nodes.
4) Call the kAltReverse() recursively for rest of the n - 2k nodes.
5) Return new head of the list.
Java
// Java program to reverse alternate k
// nodes in a linked list
class LinkedList
{
static Node head;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Reverses alternate k nodes and
returns the pointer to the new
head node */
Node kAltReverse(Node node, int k)
{
Node current = node;
Node next = null, prev = null;
int count = 0;
/ *1) reverse first k nodes of the
linked list */
while (current != null && count < k)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
/* 2) Now head points to the kth node.
So change next of head to (k+1)th node*/
if (node != null)
{
node.next = current;
}
/* 3) We do not want to reverse next
k nodes. So move the current pointer
to skip next k nodes */
count = 0;
while (count < k - 1 &&
current != null)
{
current = current.next;
count++;
}
/* 4) Recursively call for the list starting
from current->next. And make rest of the
list as next of first node */
if (current != null)
{
current.next =
kAltReverse(current.next, k);
}
/* 5) prev is new head of the
input list */
return prev;
}
void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
void push(int newdata)
{
Node mynode = new Node(newdata);
mynode.next = head;
head = mynode;
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
// Creating the linkedlist
for (int i = 20; i > 0; i--)
{
list.push(i);
}
System.out.println("Given Linked List :");
list.printList(head);
head = list.kAltReverse(head, 3);
System.out.println("");
System.out.println("Modified Linked List :");
list.printList(head);
}
}
// This code is contributed by Mayank Jaiswal
Producción:
Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
Complejidad de tiempo: O(n)
Método 2 (procesar k Nodes y llamar recursivamente al resto de la lista):
el método 1 invierte el primer k Node y luego mueve el puntero a k Nodes adelante. Entonces, el método 1 usa dos bucles while y procesa 2k Nodes en una llamada recursiva.
Este método procesa solo k Nodes en una llamada recursiva. Utiliza un tercer parámetro bool b que decide si invertir los k elementos o simplemente mover el puntero.
_kAltReverse(struct node *head, int k, bool b)
1) If b is true, then reverse first k nodes.
2) If b is false, then move the pointer k nodes ahead.
3) Call the kAltReverse() recursively for rest of the n - k nodes and link
rest of the modified list with end of first k nodes.
4) Return new head of the list.
Java
// Java program to reverse alternate
// k nodes in a linked list
class LinkedList
{
static Node head;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Alternatively reverses the given
linked list in groups of given
size k. */
Node kAltReverse(Node head, int k)
{
return _kAltReverse(head, k, true);
}
/* Helper function for kAltReverse().
It reverses k nodes of the list only
if the third parameter b is passed
as true, otherwise moves the pointer k
nodes ahead and recursively calls itself */
Node _kAltReverse(Node node,
int k, boolean b)
{
if (node == null)
{
return null;
}
int count = 1;
Node prev = null;
Node current = node;
Node next = null;
/* The loop serves two purposes
1) If b is true, then it reverses
the k nodes
2) If b is false, then it moves
the current pointer */
while (current != null && count <= k)
{
next = current.next;
/* Reverse the nodes only
if b is true*/
if (b == true)
{
current.next = prev;
}
prev = current;
current = next;
count++;
}
/* 3) If b is true, then node is the
kth node. So attach the rest of
the list after the node.
4) After attaching, return the new
head */
if (b == true)
{
node.next =
_kAltReverse(current, k, !b);
return prev;
}
/* If b is not true, then attach rest
of the list after prev. So attach rest
of the list after prev */
else
{
prev.next = _kAltReverse(current, k, !b);
return node;
}
}
void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
void push(int newdata)
{
Node mynode = new Node(newdata);
mynode.next = head;
head = mynode;
}
// Driver code
public static void main(String[] args)
{
LinkedList list = new LinkedList();
// Creating the linkedlist
for (int i = 20; i > 0; i--)
{
list.push(i);
}
System.out.println("Given Linked List :");
list.printList(head);
head = list.kAltReverse(head, 3);
System.out.println("");
System.out.println("Modified Linked List :");
list.printList(head);
}
}
// This code is contributed by Mayank Jaiswal
Producción:
Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
Complejidad de tiempo: O(n)
¡ Consulte el artículo completo sobre los Nodes K alternativos inversos en una lista enlazada individual para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA