Dada una lista enlazada, la tarea es reorganizar la lista enlazada de la siguiente manera:
- Invierta la segunda mitad de la lista enlazada dada.
-
- El primer elemento de la lista enlazada es el primer elemento de la primera mitad.
- El segundo elemento de la lista enlazada es el primer elemento de la segunda mitad.
Ejemplos:
Input: 1->2->3->4->5 Output: 1->5->2->4->3 Input: 1->2->3->4->5->6 Output: 1->6->2->5->3->4
Enfoque: Inicialmente encuentre el Node medio de la lista enlazada. El enfoque ha sido discutido aquí . Invierta la lista enlazada de la mitad al final. Una vez que se invierta la lista vinculada, recorra desde el principio e inserte un Node de la primera mitad de la lista y otro Node de la mitad posterior de la lista vinculada simultáneamente. Continúe este proceso hasta llegar al Node medio. Una vez que se alcanza el Node medio, apunte el Node justo antes del Node medio a NULL.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to sandwich the last part of
// linked list in between the first part of
// the linked list
#include<bits/stdc++.h>
#include <stdio.h>
using namespace std;
struct node {
int data;
struct node* next;
};
// Function to reverse Linked List
struct node* reverseLL(struct node* root)
{
struct node *prev = NULL, *current = root, *next;
while (current) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// root needs to be updated after reversing
root = prev;
return root;
}
// Function to modify Linked List
void modifyLL(struct node* root)
{
// Find the mid node
struct node *slow_ptr = root, *fast_ptr = root;
while (fast_ptr && fast_ptr->next) {
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
// Reverse the second half of the list
struct node* root2 = reverseLL(slow_ptr->next);
// partition the list
slow_ptr->next = NULL;
struct node *current1 = root, *current2 = root2;
// insert the elements in between
while (current1 && current2) {
// next node to be traversed in the first list
struct node* dnext1 = current1->next;
// next node to be traversed in the first list
struct node* dnext2 = current2->next;
current1->next = current2;
current2->next = dnext1;
current1 = dnext1;
current2 = dnext2;
}
}
// Function to insert node after the end
void insertNode(struct node** start, int val)
{
// allocate memory
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = val;
// if first node
if (*start == NULL)
*start = temp;
else {
// move to the end pointer of node
struct node* dstart = *start;
while (dstart->next != NULL)
dstart = dstart->next;
dstart->next = temp;
}
}
// function to print the linked list
void display(struct node** start)
{
struct node* temp = *start;
// traverse till the entire linked
// list is printed
while (temp->next != NULL) {
printf("%d->", temp->data);
temp = temp->next;
}
printf("%d\n", temp->data);
}
// Driver Code
int main()
{
// Odd Length Linked List
struct node* start = NULL;
insertNode(&start, 1);
insertNode(&start, 2);
insertNode(&start, 3);
insertNode(&start, 4);
insertNode(&start, 5);
printf("Before Modifying: ");
display(&start);
modifyLL(start);
printf("After Modifying: ");
display(&start);
// Even Length Linked List
start = NULL;
insertNode(&start, 1);
insertNode(&start, 2);
insertNode(&start, 3);
insertNode(&start, 4);
insertNode(&start, 5);
insertNode(&start, 6);
printf("\nBefore Modifying: ");
display(&start);
modifyLL(start);
printf("After Modifying: ");
display(&start);
return 0;
}
Java
// Java program to sandwich the
// last part of linked list in
// between the first part of
// the linked list
import java.util.*;
class node
{
int data;
node next;
node(int key)
{
data = key;
next = null;
}
}
class GFG
{
// Function to reverse
// Linked List
public static node reverseLL(node root)
{
node prev = null,
current = root, next;
while (current!= null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
// root needs to be
// updated after reversing
root = prev;
return root;
}
// Function to modify
// Linked List
public static void modifyLL( node root)
{
// Find the mid node
node slow_ptr = root, fast_ptr = root;
while (fast_ptr != null &&
fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
// Reverse the second
// half of the list
node root2 = reverseLL(slow_ptr.next);
// partition the list
slow_ptr.next = null;
node current1 = root,
current2 = root2;
// insert the elements in between
while (current1 != null &&
current2 != null)
{
// next node to be traversed
// in the first list
node dnext1 = current1.next;
// next node to be traversed
// in the first list
node dnext2 = current2.next;
current1.next = current2;
current2.next = dnext1;
current1 = dnext1;
current2 = dnext2;
}
}
// Function to insert
// node after the end
public static node insertNode(node start,
int val)
{
// allocate memory
node temp = new node(val);
// if first node
if (start == null)
start = temp;
else
{
// move to the end
// pointer of node
node dstart = start;
while (dstart.next != null)
dstart = dstart.next;
dstart.next = temp;
}
return start;
}
// function to print
// the linked list
public static void display(node start)
{
node temp = start;
// traverse till the
// entire linked
// list is printed
while (temp.next != null) {
System.out.print(temp.data + "->");
temp = temp.next;
}
System.out.println(temp.data);
}
// Driver Code
public static void main(String args[])
{
// Odd Length Linked List
node start = null;
start = insertNode(start, 1);
start = insertNode(start, 2);
start = insertNode(start, 3);
start = insertNode(start, 4);
start = insertNode(start, 5);
System.out.print("Before Modifying: ");
display(start);
modifyLL(start);
System.out.print("After Modifying: ");
display(start);
// Even Length Linked List
start = null;
start = insertNode(start, 1);
start = insertNode(start, 2);
start = insertNode(start, 3);
start = insertNode(start, 4);
start = insertNode(start, 5);
start = insertNode(start, 6);
System.out.print("Before Modifying: ");
display(start);
modifyLL(start);
System.out.print("After Modifying: ");
display(start);
}
}
Python3
# Python3 program to sandwich the last part of
# linked list in between the first part of
# the linked list
class node:
def __init__(self):
self.data = 0
self.next = None
# Function to reverse Linked List
def reverseLL(root):
prev = None
current = root
while (current):
next = current.next;
current.next = prev;
prev = current;
current = next;
# root needs to be updated after reversing
root = prev;
return root;
# Function to modify Linked List
def modifyLL(root):
# Find the mid node
slow_ptr = root
fast_ptr = root;
while (fast_ptr and fast_ptr.next):
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
# Reverse the second half of the list
root2 = reverseLL(slow_ptr.next);
# partition the list
slow_ptr.next = None;
current1 = root
current2 = root2;
# insert the elements in between
while (current1 and current2):
# next node to be traversed in the first list
dnext1 = current1.next;
# next node to be traversed in the first list
dnext2 = current2.next;
current1.next = current2;
current2.next = dnext1;
current1 = dnext1;
current2 = dnext2;
# Function to insert node after the end
def insertNode(start, val):
# allocate memory
temp = node()
temp.data = val;
# if first node
if (start == None):
start = temp;
else:
# move to the end pointer of node
dstart = start;
while (dstart.next != None):
dstart = dstart.next;
dstart.next = temp;
return start
# function to print the linked list
def display(start):
temp = start;
# traverse till the entire linked
# list is printed
while (temp.next != None):
print("{}->".format(temp.data), end = '')
temp = temp.next;
print("{}".format(temp.data))
# Driver Code
if __name__=='__main__':
# Odd Length Linked List
start = None;
start = insertNode(start, 1);
start = insertNode(start, 2);
start = insertNode(start, 3);
start = insertNode(start, 4);
start = insertNode(start, 5);
print("Before Modifying: ", end = '');
display(start);
modifyLL(start);
print("After Modifying: ", end = '');
display(start);
# Even Length Linked List
start = None;
start = insertNode(start, 1);
start = insertNode(start, 2);
start = insertNode(start, 3);
start = insertNode(start, 4);
start = insertNode(start, 5);
start = insertNode(start, 6);
print("\nBefore Modifying: ", end = '');
display(start);
modifyLL(start);
print("After Modifying: ", end = '')
display(start);
# This code is contributed by rutvik_56
C#
// C# program to sandwich the last part
// of linked list in between the first
// part of the linked list
using System;
public class node
{
public int data;
public node next;
public node(int key)
{
data = key;
next = null;
}
}
public class GFG
{
// Function to reverse
// Linked List
public static node reverseLL(node root)
{
node prev = null,
current = root, next;
while (current!= null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
// root needs to be
// updated after reversing
root = prev;
return root;
}
// Function to modify
// Linked List
public static void modifyLL( node root)
{
// Find the mid node
node slow_ptr = root, fast_ptr = root;
while (fast_ptr != null &&
fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
// Reverse the second
// half of the list
node root2 = reverseLL(slow_ptr.next);
// partition the list
slow_ptr.next = null;
node current1 = root,
current2 = root2;
// insert the elements in between
while (current1 != null &&
current2 != null)
{
// next node to be traversed
// in the first list
node dnext1 = current1.next;
// next node to be traversed
// in the first list
node dnext2 = current2.next;
current1.next = current2;
current2.next = dnext1;
current1 = dnext1;
current2 = dnext2;
}
}
// Function to insert
// node after the end
public static node insertNode(node start,
int val)
{
// allocate memory
node temp = new node(val);
// if first node
if (start == null)
start = temp;
else
{
// move to the end
// pointer of node
node dstart = start;
while (dstart.next != null)
dstart = dstart.next;
dstart.next = temp;
}
return start;
}
// function to print
// the linked list
public static void display(node start)
{
node temp = start;
// traverse till the
// entire linked
// list is printed
while (temp.next != null)
{
Console.Write(temp.data + "->");
temp = temp.next;
}
Console.WriteLine(temp.data);
}
// Driver Code
public static void Main(String []args)
{
// Odd Length Linked List
node start = null;
start = insertNode(start, 1);
start = insertNode(start, 2);
start = insertNode(start, 3);
start = insertNode(start, 4);
start = insertNode(start, 5);
Console.Write("Before Modifying: ");
display(start);
modifyLL(start);
Console.Write("After Modifying: ");
display(start);
// Even Length Linked List
start = null;
start = insertNode(start, 1);
start = insertNode(start, 2);
start = insertNode(start, 3);
start = insertNode(start, 4);
start = insertNode(start, 5);
start = insertNode(start, 6);
Console.Write("Before Modifying: ");
display(start);
modifyLL(start);
Console.Write("After Modifying: ");
display(start);
}
}
// This code has been contributed
// by 29AjayKumar
Javascript
<script>
// JavaScript program to sandwich the last part
// of linked list in between the first
// part of the linked list
class node {
constructor(key) {
this.data = key;
this.next = null;
}
}
// Function to reverse
// Linked List
function reverseLL(root) {
var prev = null,
current = root,
next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
// root needs to be
// updated after reversing
root = prev;
return root;
}
// Function to modify
// Linked List
function modifyLL(root)
{
// Find the mid node
var slow_ptr = root,
fast_ptr = root;
while (fast_ptr != null && fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
// Reverse the second
// half of the list
var root2 = reverseLL(slow_ptr.next);
// partition the list
slow_ptr.next = null;
var current1 = root,
current2 = root2;
// insert the elements in between
while (current1 != null && current2 != null)
{
// next node to be traversed
// in the first list
var dnext1 = current1.next;
// next node to be traversed
// in the first list
var dnext2 = current2.next;
current1.next = current2;
current2.next = dnext1;
current1 = dnext1;
current2 = dnext2;
}
}
// Function to insert
// node after the end
function insertNode(start, val)
{
// allocate memory
var temp = new node(val);
// if first node
if (start == null) start = temp;
else
{
// move to the end
// pointer of node
var dstart = start;
while (dstart.next != null) dstart = dstart.next;
dstart.next = temp;
}
return start;
}
// function to print
// the linked list
function display(start) {
var temp = start;
// traverse till the
// entire linked
// list is printed
while (temp.next != null) {
document.write(temp.data + "->");
temp = temp.next;
}
document.write(temp.data + "<br>");
}
// Driver Code
// Odd Length Linked List
var start = null;
start = insertNode(start, 1);
start = insertNode(start, 2);
start = insertNode(start, 3);
start = insertNode(start, 4);
start = insertNode(start, 5);
document.write("Before Modifying: ");
display(start);
modifyLL(start);
document.write("After Modifying: ");
display(start);
// Even Length Linked List
start = null;
start = insertNode(start, 1);
start = insertNode(start, 2);
start = insertNode(start, 3);
start = insertNode(start, 4);
start = insertNode(start, 5);
start = insertNode(start, 6);
document.write("<br>Before Modifying: ");
display(start);
modifyLL(start);
document.write("After Modifying: ");
display(start);
// This code is contributed by rdtank.
</script>
Producción:
Before Modifying: 1->2->3->4->5 After Modifying: 1->5->2->4->3 Before Modifying: 1->2->3->4->5->6 After Modifying: 1->6->2->5->3->4
Complejidad de Tiempo: O(N)
Ejercicio: Resuelva la pregunta sin invertir la Lista Vinculada desde el Node medio.
Publicación traducida automáticamente
Artículo escrito por HarshaSridhar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA