# 算法设计：反转链表代码实现

2021年4月14日14:08:46 发表评论 550 次浏览

## C ++

``````//Iterative C++ program to reverse
#include <iostream>
using namespace std;

struct Node {
int data;
struct Node* next;
Node( int data)
{
this ->data = data;
next = NULL;
}
};

{
}

/* Function to reverse the linked list */
void reverse()
{
//Initialize current, previous and
//next pointers
Node *prev = NULL, *next = NULL;

while (current != NULL) {
//Store next
next = current->next;

//Reverse current node's pointer
current->next = prev;

prev = current;
current = next;
}
}

/* Function to print linked list */
void print()
{
while (temp != NULL) {
cout <<temp->data <<" " ;
temp = temp->next;
}
}

void push( int data)
{
Node* temp = new Node(data);
}
};

/* Driver program to test above function*/
int main()
{
ll.push(20);
ll.push(4);
ll.push(15);
ll.push(85);

ll.print();

ll.reverse();

cout <<"\nReversed Linked list \n" ;
ll.print();
return 0;
}``````

## C

``````//Iterative C program to reverse a linked list
#include <stdio.h>
#include <stdlib.h>

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

/* Function to reverse the linked list */
static void reverse( struct Node** head_ref)
{
struct Node* prev = NULL;
struct Node* next = NULL;
while (current != NULL) {
//Store next
next = current->next;

//Reverse current node's pointer
current->next = prev;

prev = current;
current = next;
}
}

/* 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;
}

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

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

printf ( "Given linked list\n" );
printf ( "\nReversed Linked list \n" );
getchar ();
}``````

## Java

``````//Java program for reversing the linked list

static class Node {

int data;
Node next;

Node( int d)
{
data = d;
next = null ;
}
}

/* Function to reverse the linked list */
Node reverse(Node node)
{
Node prev = null ;
Node current = node;
Node next = null ;
while (current != null ) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}

//prints content of double linked list
void printList(Node node)
{
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}

public static void main(String[] args)
{
list.head = new Node( 85 );
list.head.next = new Node( 15 );
list.head.next.next = new Node( 4 );
list.head.next.next.next = new Node( 20 );

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

//This code has been contributed by Mayank Jaiswal``````

## python

``````# Python program to reverse a linked list
# Time Complexity : O(n)
# Space Complexity : O(1)

# Node class
class Node:

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

def __init__( self ):

# Function to reverse the linked list
def reverse( self ):
prev = None
while (current is not None ):
next = current. next
current. next = prev
prev = current
current = next

# Function to insert a new node at the beginning
def push( self , new_data):
new_node = Node(new_data)

def printList( self ):
while (temp):
print temp.data, temp = temp. next

# Driver program to test above functions
llist.push( 20 )
llist.push( 4 )
llist.push( 15 )
llist.push( 85 )

llist.printList()
llist.reverse()
llist.printList()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)``````

## C#

``````//C# program for reversing the linked list
using System;

class GFG {
static void Main( string [] args)
{

//List before reversal
list.PrintList();

//Reverse the list
list.ReverseList();

//List after reversal
list.PrintList();
}
}

public class Node {
public int data;
public Node next;

public Node( int d)
{
data = d;
next = null ;
}
}

//function to add a new node at
//the end of the list
{
else {
while (temp.next != null ) {
temp = temp.next;
}
temp.next = node;
}
}

//function to reverse the list
public void ReverseList()
{
Node prev = null , current = head, next = null ;
while (current != null ) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
}

//function to print the list data
public void PrintList()
{
while (current != null ) {
Console.Write(current.data + " " );
current = current.next;
}
Console.WriteLine();
}
}

//This code is contributed by Mayank Sharma``````

``````Given linked list
85 15 4 20
20 4 15 85``````

``````1) Divide the list in two parts - first node and
2) Call reverse for the rest of the linked list.

## C ++

``````//Recursive C++ program to reverse
#include <iostream>
using namespace std;

struct Node {
int data;
struct Node* next;
Node( int data)
{
this ->data = data;
next = NULL;
}
};

{
}

{

/* reverse the rest list and put
the first element at the end */

/* tricky step -- see the diagram */

/* fix the head pointer */
return rest;
}

/* Function to print linked list */
void print()
{
while (temp != NULL) {
cout <<temp->data <<" " ;
temp = temp->next;
}
}

void push( int data)
{
Node* temp = new Node(data);
}
};

/* Driver program to test above function*/
int main()
{
ll.push(20);
ll.push(4);
ll.push(15);
ll.push(85);

ll.print();

cout <<"\nReversed Linked list \n" ;
ll.print();
return 0;
}``````

## Java

``````//Recursive Java program to reverse
class recursion {

static class Node {
int data;
Node next;
Node( int d)
{
data = d;
next = null ;
}
}

{

/* reverse the rest list and put
the first element at the end */

/* tricky step -- see the diagram */

/* fix the head pointer */
return rest;
}

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

static void push( int data)
{
Node temp = new Node(data);
}

/* Driver program to test above function*/
public static void main(String args[])
{

push( 20 );
push( 4 );
push( 15 );
push( 85 );

print();

print();
}
}

//This code is contributed by Prakhar Agarwal``````

## Python3

``````"""Python3 program to reverse linked list
using recursive method"""

class Node:
def __init__( self , data):
self .data = data
self . next = None

# Create and Handle list operations
def __init__( self ):

# Method to reverse the list

# If head is empty or has reached the list end

# Reverse the rest list
rest = self .reverse(head. next )

# Put first element at the end

return rest

# Returns the linked list in display format
def __str__( self ):
while temp:
str (temp.data) + " " )
temp = temp. next

# Pushes new data to the head of the list
def push( self , data):
temp = Node(data)

# Driver code

print ( "Given linked list" )

print ( "Reversed linked list" )

# This code is contributed by Debidutta Rath``````

## C#

``````//Recursive C# program to
using System;
class recursion{

public class Node
{
public int data;
public Node next;
public Node( int d)
{
data = d;
next = null ;
}
}

{

//Reverse the rest list and put
//the first element at the end

//Tricky step --
//see the diagram

return rest;
}

//Function to print
static void print()
{
while (temp != null )
{
Console.Write(temp.data + " " );
temp = temp.next;
}
Console.WriteLine();
}

static void push( int data)
{
Node temp = new Node(data);
}

//Driver code
public static void Main(String []args)
{
//empty list
push(20);
push(4);
push(15);
push(85);

print();
print();
}
}

//This code is contributed by gauravrajput1``````

``````Given linked list
85 15 4 20
20 4 15 85``````

O(1)

## C ++

``````//A simple and tail recursive C++ program to reverse
#include <bits/stdc++.h>
using namespace std;

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

void reverseUtil(Node* curr, Node* prev, Node** head);

//This function mainly calls reverseUtil()
//with prev as NULL
{
return ;
}

//A simple and tail-recursive function to reverse
//a linked list.  prev is passed as NULL initially.
void reverseUtil(Node* curr, Node* prev, Node** head)
{
/* If last node mark it head*/
if (!curr->next) {

/* Update next to prev node */
curr->next = prev;
return ;
}

/* Save curr->next node for recursive call */
Node* next = curr->next;

/* and update next ..*/
curr->next = prev;

}

//A utility function to create a new node
Node* newNode( int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}

//A utility function to print a linked list
{
}
cout <<endl;
}

//Driver program to test above functions
int main()
{
return 0;
}``````

## Java

``````//Java program for reversing the Linked list

static class Node {

int data;
Node next;

Node( int d)
{
data = d;
next = null ;
}
}

//A simple and tail recursive function to reverse
//a linked list.  prev is passed as NULL initially.
Node reverseUtil(Node curr, Node prev)
{

/* If last node mark it head*/
if (curr.next == null ) {

/* Update next to prev node */
curr.next = prev;

}

/* Save curr->next node for recursive call */
Node next1 = curr.next;

/* and update next ..*/
curr.next = prev;

reverseUtil(next1, curr);
}

//prints content of double linked list
void printList(Node node)
{
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}

public static void main(String[] args)
{
list.head = new Node( 1 );
list.head.next = new Node( 2 );
list.head.next.next = new Node( 3 );
list.head.next.next.next = new Node( 4 );
list.head.next.next.next.next = new Node( 5 );
list.head.next.next.next.next.next = new Node( 6 );
list.head.next.next.next.next.next.next = new Node( 7 );
list.head.next.next.next.next.next.next.next = new Node( 8 );

System.out.println( "Original Linked list " );
Node res = list.reverseUtil(head, null );
System.out.println( "" );
System.out.println( "" );
System.out.println( "Reversed linked list " );
list.printList(res);
}
}

//This code has been contributed by Mayank Jaiswal``````

## python

``````# Simple and tail recursive Python program to

# Node class
class Node:

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

def __init__( self ):

def reverseUtil( self , curr, prev):

# If last node mark it head
if curr. next is None :

# Update next to prev node
curr. next = prev
return

# Save curr.next node for recursive call
next = curr. next

# And update next
curr. next = prev

self .reverseUtil( next , curr)

# This function mainly calls reverseUtil()
# with previous as None
def reverse( self ):
if self .head is None :
return
self .reverseUtil( self .head, None )

# Function to insert a new node at the beginning
def push( self , new_data):
new_node = Node(new_data)

def printList( self ):
while (temp):
print temp.data, temp = temp. next

# Driver program
llist.push( 8 )
llist.push( 7 )
llist.push( 6 )
llist.push( 5 )
llist.push( 4 )
llist.push( 3 )
llist.push( 2 )
llist.push( 1 )

llist.printList()

llist.reverse()

llist.printList()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)``````

## C#

``````//C# program for reversing the Linked list
using System;

public class Node {

public int data;
public Node next;

public Node( int d)
{
data = d;
next = null ;
}
}

//A simple and tail-recursive function to reverse
//a linked list. prev is passed as NULL initially.
Node reverseUtil(Node curr, Node prev)
{

/* If last node mark it head*/
if (curr.next == null ) {

/* Update next to prev node */
curr.next = prev;

}

/* Save curr->next node for recursive call */
Node next1 = curr.next;

/* and update next ..*/
curr.next = prev;

reverseUtil(next1, curr);
}

//prints content of double linked list
void printList(Node node)
{
while (node != null ) {
Console.Write(node.data + " " );
node = node.next;
}
}

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

Console.WriteLine( "Original Linked list " );
Node res = list.reverseUtil(list.head, null );
Console.WriteLine( "" );
Console.WriteLine( "" );
Console.WriteLine( "Reversed linked list " );
list.printList(res);
}
}

//This code contributed by Rajput-Ji``````

``````Given linked list
1 2 3 4 5 6 7 8

8 7 6 5 4 3 2 1``````

• 将节点(值和地址)存储在堆栈中, 直到输入所有值。
• 开始弹出节点(值和地址)并以相同顺序存储它们, 直到堆栈为空。
• 用NULL更新堆栈中最后一个节点的下一个指针。

## C ++

``````//C++ program for above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

//Create a class Node to enter
//values and address in the list
class Node
{
public :
int data;
Node* next;
};

//Function to reverse the
{

//Create a stack "s"
//of Node type
stack<Node*> s;
while (temp->next != NULL)
{

//Push all the nodes
//in to stack
s.push(temp);
temp = temp->next;
}

while (!s.empty())
{

//Store the top value of
//stack in list
temp->next = s.top();

//Pop the value from stack
s.pop();

//update the next pointer in the
//in the list
temp = temp->next;
}
temp->next = NULL;
}

//Function to Display
//the elements in List
void printlist(Node* temp)
{
while (temp != NULL)
{
cout <<temp->data <<" " ;
temp = temp->next;
}
}

//Program to insert back of the
{

//we have used insertion at back method
//to enter values in the list.(eg:
Node* temp = new Node();
temp->data = value;
temp->next = NULL;

{
return ;
}
else
{
while (last_node->next != NULL)
{
last_node = last_node->next;
}
last_node->next = temp;
return ;
}
}

//Driver Code
int main()
{

return 0;
}``````

``````Given linked list
1 2 3 4