算法设计：以给定大小的组反向链表|套装2

2021年3月9日16:04:46 发表评论 377 次浏览

本文概述

``````Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3
Output:  3->2->1->6->5->4->8->7->NULL.

Inputs:   1->2->3->4->5->6->7->8->NULL and k = 5
Output:  5->4->3->2->1->8->7->6->NULL.``````

C ++

``````// C++ program to reverse a linked list in groups
// of given size
#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
struct Node* next;
};

/* Reverses the linked list in groups of size k
and returns the pointer to the new head node. */
struct Node* Reverse( struct Node* head, int k)
{
// Create a stack of Node*
stack<Node*> mystack;
struct Node* prev = NULL;

while (current != NULL) {

// Terminate the loop whichever comes first
// either current == NULL or count >= k
int count = 0;
while (current != NULL && count < k) {
mystack.push(current);
current = current->next;
count++;
}

// Now pop the elements of stack one by one
while (mystack.size() > 0) {

// If final list has not been started yet.
if (prev == NULL) {
prev = mystack.top();
mystack.pop();
} else {
prev->next = mystack.top();
prev = prev->next;
mystack.pop();
}
}
}

// Next of last element will point to NULL.
prev->next = NULL;

}

/* UTILITY FUNCTIONS */
/* Function to push a node */
void push( struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
( struct Node*) malloc ( sizeof ( struct Node));

/* put in the data  */
new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
void printList( struct Node* node)
{
while (node != NULL) {
printf ( "%d  " , node->data);
node = node->next;
}
}

/* Driver program to test above function*/
int main( void )
{

/* Created Linked list is 1->2->3->4->5->6->7->8->9 */

printf ( "\nGiven linked list \n" );

printf ( "\nReversed Linked list \n" );

return 0;
}``````

Java

``````// Java program to reverse a linked list in groups
// of given size
import java.util.*;
class GfG
{

static class Node
{
int data;
Node next;
}
static Node head = null ;

/* Reverses the linked list in groups of size k
and returns the pointer to the new head node. */
static Node Reverse(Node head, int k)
{
// Create a stack of Node*
Stack<Node> mystack = new Stack<Node> ();
Node prev = null ;

while (current != null )
{

// Terminate the loop whichever comes first
// either current == NULL or count >= k
int count = 0 ;
while (current != null && count < k)
{
mystack.push(current);
current = current.next;
count++;
}

// Now pop the elements of stack one by one
while (mystack.size() > 0 )
{

// If final list has not been started yet.
if (prev == null )
{
prev = mystack.peek();
mystack.pop();
}
else
{
prev.next = mystack.peek();
prev = prev.next;
mystack.pop();
}
}
}

// Next of last element will point to NULL.
prev.next = null ;

}

/* UTILITY FUNCTIONS */
/* Function to push a node */
static void push( int new_data)
{
/* allocate node */
Node new_node = new Node();

/* put in the data */
new_node.data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
static void printList(Node node)
{
while (node != null )
{
System.out.print(node.data + " " );
node = node.next;
}
}

/* Driver code*/
public static void main(String[] args)
{

/* Created Linked list is 1->2->3->
4->5->6->7->8->9 */
push( 9 );
push( 8 );
push( 7 );
push( 6 );
push( 5 );
push( 4 );
push( 3 );
push( 2 );
push( 1 );

System.out.println( "Given linked list " );
System.out.println();

System.out.println( "Reversed Linked list " );
}
}

// This code is contributed by Prerna Saini``````

Python3

``````# Python3 program to reverse a Linked List
# in groups of given size

# Node class
class Node( object ):
__slots__ = 'data' , 'next'

# Constructor to initialize the node object
def __init__( self , data = None , next = None ):
self .data = data
self . next = next

def __repr__( self ):
return repr ( self .data)

def __init__( self ):

# Utility function to print nodes
def __repr__( self ):
nodes = []
while curr:
nodes.append( repr (curr))
curr = curr. next
return '[' + ', ' .join(nodes) + ']'

# Function to insert a new node at
# the beginning
def prepend( self , data):

# Reverses the linked list in groups of size k
# and returns the pointer to the new head node.
def reverse( self , k = 1 ):
if self .head is None :
return

prev = None
new_stack = []
while curr is not None :
val = 0

# Terminate the loop whichever comes first
# either current == None or value >= k
while curr is not None and val < k:
new_stack.append(curr.data)
curr = curr. next
val + = 1

# Now pop the elements of stack one by one
while new_stack:

# If final list has not been started yet.
if prev is None :
prev = Node(new_stack.pop())
else :
prev. next = Node(new_stack.pop())
prev = prev. next

# Next of last element will point to None.
prev. next = None

# Driver Code
llist.prepend( 9 )
llist.prepend( 8 )
llist.prepend( 7 )
llist.prepend( 6 )
llist.prepend( 5 )
llist.prepend( 4 )
llist.prepend( 3 )
llist.prepend( 2 )
llist.prepend( 1 )

print ( "Given linked list" )
print (llist)

print ( "Reversed Linked list" )
print (llist)

# This code is contributed by
# Sagar Kumar Sinha(sagarsinha7777)``````

C#

``````// C# program to reverse a linked list
// in groups of given size
using System;
using System.Collections;

class GfG
{

public class Node
{
public int data;
public Node next;
}
static Node head = null ;

/* Reverses the linked list in groups of size k
and returns the pointer to the new head node. */
static Node Reverse(Node head, int k)
{
// Create a stack of Node*
Stack mystack = new Stack();
Node prev = null ;

while (current != null )
{

// Terminate the loop whichever comes first
// either current == NULL or count >= k
int count = 0;
while (current != null && count < k)
{
mystack.Push(current);
current = current.next;
count++;
}

// Now Pop the elements of stack one by one
while (mystack.Count > 0)
{

// If final list has not been started yet.
if (prev == null )
{
prev = (Node)mystack.Peek();
mystack.Pop();
}
else
{
prev.next = (Node)mystack.Peek();
prev = prev.next;
mystack.Pop();
}
}
}

// Next of last element will point to NULL.
prev.next = null ;

}

/* UTILITY FUNCTIONS */
/* Function to Push a node */
static void Push( int new_data)
{
/* allocate node */
Node new_node = new Node();

/* put in the data */
new_node.data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
static void printList(Node node)
{
while (node != null )
{
Console.Write(node.data + " " );
node = node.next;
}
}

/* Driver code*/
public static void Main(String []args)
{

/* Created Linked list is 1->2->3->
4->5->6->7->8->9 */
Push( 9);
Push( 8);
Push( 7);
Push( 6);
Push( 5);
Push(4);
Push(3);
Push(2);
Push( 1);

Console.WriteLine( "Given linked list " );
Console.WriteLine();

Console.WriteLine( "Reversed Linked list " );
}
}

// This code is contributed by Arnab Kundu``````

``````Given Linked List
1 2 3 4 5 6 7 8 9
Reversed list
3 2 1 6 5 4 9 8 7``````

• A+