Invertir los primeros elementos K de la lista enlazada dada

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *