Dado un puntero al Node principal de una lista enlazada y un número K, la tarea es invertir los primeros K Nodes de la lista enlazada. Necesitamos invertir la lista cambiando los enlaces entre los Nodes.
verifique también Inversión de una lista enlazada
Ejemplos:
C++
// C++ program for reversal of first k elements
// of given linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to reverse first k elements of linked list */
static void reverseKNodes(struct Node** head_ref, int k)
{
// traverse the linked list until break
// point not meet
struct Node* temp = *head_ref;
int count = 1;
while (count < k) {
temp = temp->next;
count++;
}
// backup the joint point
struct Node* joint_point = temp->next;
temp->next = NULL; // break the list
// reverse the list till break point
struct Node* prev = NULL;
struct Node* current = *head_ref;
struct Node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// join both parts of the linked list
// traverse the list until NULL is not
// found
*head_ref = prev;
current = *head_ref;
while (current->next != NULL)
current = current->next;
// joint both part of the list
current->next = joint_point;
}
/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test above function*/
int main()
{
// Create a linked list 1->2->3->4->5
struct Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
// k should be less than the
// numbers of nodes
int k = 3;
cout << "\nGiven list\n";
printList(head);
reverseKNodes(&head, k);
cout << "\nModified list\n";
printList(head);
return 0;
}
Java
// Java program for reversal of first k elements
// of given linked list
class Sol
{
// Link list node
static class Node
{
int data;
Node next;
};
// Function to reverse first k elements of linked list
static Node reverseKNodes( Node head_ref, int k)
{
// traverse the linked list until break
// point not meet
Node temp = head_ref;
int count = 1;
while (count < k)
{
temp = temp.next;
count++;
}
// backup the joint point
Node joint_point = temp.next;
temp.next = null; // break the list
// reverse the list till break point
Node prev = null;
Node current = head_ref;
Node next;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
// join both parts of the linked list
// traverse the list until null is not
// found
head_ref = prev;
current = head_ref;
while (current.next != null)
current = current.next;
// joint both part of the list
current.next = joint_point;
return head_ref;
}
// Function to push a node
static Node push( Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Function to print linked list
static void printList( Node head)
{
Node temp = head;
while (temp != null)
{
System.out.printf("%d ", temp.data);
temp = temp.next;
}
}
// Driver program to test above function
public static void main(String args[])
{
// Create a linked list 1.2.3.4.5
Node head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
// k should be less than the
// numbers of nodes
int k = 3;
System.out.print("\nGiven list\n");
printList(head);
head = reverseKNodes(head, k);
System.out.print("\nModified list\n");
printList(head);
}
}
// This code is contributed by Arnab Kundu
Python
# Python program for reversal of first k elements
# of given linked list
# Node of a linked list
class Node:
def __init__(self, next = None, data = None):
self.next = next
self.data = data
# Function to reverse first k elements of linked list
def reverseKNodes(head_ref, k) :
# traverse the linked list until break
# point not meet
temp = head_ref
count = 1
while (count < k):
temp = temp.next
count = count + 1
# backup the joint point
joint_point = temp.next
temp.next = None # break the list
# reverse the list till break point
prev = None
current = head_ref
next = None
while (current != None):
next = current.next
current.next = prev
prev = current
current = next
# join both parts of the linked list
# traverse the list until None is not
# found
head_ref = prev
current = head_ref
while (current.next != None):
current = current.next
# joint both part of the list
current.next = joint_point
return head_ref
# Function to push a node
def push(head_ref, new_data) :
new_node = Node()
new_node.data = new_data
new_node.next = (head_ref)
(head_ref) = new_node
return head_ref
# Function to print linked list
def printList( head) :
temp = head
while (temp != None):
print(temp.data, end = " ")
temp = temp.next
# Driver program to test above function
# Create a linked list 1.2.3.4.5
head = None
head = push(head, 5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
# k should be less than the
# numbers of nodes
k = 3
print("\nGiven list")
printList(head)
head = reverseKNodes(head, k)
print("\nModified list")
printList(head)
# This code is contributed by Arnab Kundu
C#
// C# program for reversal of first k elements
// of given linked list
using System;
class GFG
{
// Link list node
public class Node
{
public int data;
public Node next;
};
// Function to reverse first k elements of linked list
static Node reverseKNodes(Node head_ref, int k)
{
// traverse the linked list until break
// point not meet
Node temp = head_ref;
int count = 1;
while (count < k)
{
temp = temp.next;
count++;
}
// backup the joint point
Node joint_point = temp.next;
temp.next = null; // break the list
// reverse the list till break point
Node prev = null;
Node current = head_ref;
Node next;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
// join both parts of the linked list
// traverse the list until null is not
// found
head_ref = prev;
current = head_ref;
while (current.next != null)
current = current.next;
// joint both part of the list
current.next = joint_point;
return head_ref;
}
// Function to push a node
static Node push( Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Function to print linked list
static void printList( Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write("{0} ", temp.data);
temp = temp.next;
}
}
// Driver Code
public static void Main(String []args)
{
// Create a linked list 1.2.3.4.5
Node head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
// k should be less than the
// numbers of nodes
int k = 3;
Console.Write("Given list\n");
printList(head);
head = reverseKNodes(head, k);
Console.Write("\nModified list\n");
printList(head);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for reversal of first k elements
// of given linked list
// Link list node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
};
// Function to reverse first k elements of linked list
function reverseKNodes(head_ref, k)
{
// traverse the linked list until break
// point not meet
var temp = head_ref;
var count = 1;
while (count < k)
{
temp = temp.next;
count++;
}
// backup the joint point
var joint_point = temp.next;
temp.next = null; // break the list
// reverse the list till break point
var prev = null;
var current = head_ref;
var next;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
// join both parts of the linked list
// traverse the list until null is not
// found
head_ref = prev;
current = head_ref;
while (current.next != null)
current = current.next;
// joint both part of the list
current.next = joint_point;
return head_ref;
}
// Function to push a node
function push( head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Function to print linked list
function printList( head)
{
var temp = head;
while (temp != null)
{
document.write(temp.data+ " ");
temp = temp.next;
}
}
// Driver Code
// Create a linked list 1.2.3.4.5
var head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
// k should be less than the
// numbers of nodes
var k = 3;
document.write("Given list<br>");
printList(head);
head = reverseKNodes(head, k);
document.write("<br>Modified list<br>");
printList(head);
</script>
Publicación traducida automáticamente
Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA