# 算法设计：如何检查两个相同的链表？

2021年3月18日14:46:11 发表评论 338 次浏览

## C ++

``````// An iterative C++ program to check if
// two linked lists are identical or not
#include<bits/stdc++.h>
using namespace std;

/* Structure for a linked list node */
struct Node
{
int data;
struct Node *next;
};

/* Returns true if linked lists a and b
are identical, otherwise false */
bool areIdentical( struct Node *a, struct Node *b)
{
while (a != NULL && b != NULL)
{
if (a->data != b->data)
return false ;

/* If we reach here, then a and b are
not NULL and their data is same, so
move to next nodes in both lists */
a = a->next;
b = b->next;
}

// If linked lists are identical, then
// 'a' and 'b' must be NULL at this point.
return (a == NULL && b == NULL);
}

/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the
head of a list and an int, push a new node on the
front of the list. */
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 */
}

// Driver Code
int main()
{
/* The constructed linked lists are :
a: 3->2->1
b: 3->2->1 */
struct Node *a = NULL;
struct Node *b = NULL;
push(&a, 1);
push(&a, 2);
push(&a, 3);
push(&b, 1);
push(&b, 2);
push(&b, 3);

if (areIdentical(a, b))
cout << "Identical" ;
else
cout << "Not identical" ;

return 0;
}

// This code is contributed
// by Akanksha Rai``````

## C

``````// An iterative C program to check if two linked lists are
// identical or not
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

/* Structure for a linked list node */
struct Node
{
int data;
struct Node *next;
};

/* Returns true if linked lists a and b are identical, otherwise false */
bool areIdentical( struct Node *a, struct Node *b)
{
while (a != NULL && b != NULL)
{
if (a->data != b->data)
return false ;

/* If we reach here, then a and b are not NULL and
their data is same, so move to next nodes in both
lists */
a = a->next;
b = b->next;
}

// If linked lists are identical, then 'a' and 'b' must
// be NULL at this point.
return (a == NULL && b == NULL);
}

/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
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 */
}

/* Driver program to test above function */
int main()
{
/* The constructed linked lists are :
a: 3->2->1
b: 3->2->1 */
struct Node *a = NULL;
struct Node *b = NULL;
push(&a, 1);
push(&a, 2);
push(&a, 3);
push(&b, 1);
push(&b, 2);
push(&b, 3);

areIdentical(a, b)? printf ( "Identical" ):
printf ( "Not identical" );

return 0;
}``````

## Java

``````// An iterative Java program to check if two linked lists
// are identical or not
{

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

/* Returns true if linked lists a and b are identical, otherwise false */
{
while (a != null && b != null )
{
if (a.data != b.data)
return false ;

/* If we reach here, then a and b are not null
and their data is same, so move to next nodes
in both lists */
a = a.next;
b = b.next;
}

// If linked lists are identical, then 'a' and 'b' must
// be null at this point.
return (a == null && b == null );
}

/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/*  Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */

void push( int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

/* 4. Move the head to point to new Node */
}

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

/* The constructed linked lists are :
llist1: 3->2->1
llist2: 3->2->1 */

llist1.push( 1 );
llist1.push( 2 );
llist1.push( 3 );

llist2.push( 1 );
llist2.push( 2 );
llist2.push( 3 );

if (llist1.areIdentical(llist2) == true )
System.out.println( "Identical " );
else
System.out.println( "Not identical " );

}
} /* This code is contributed by Rajat Mishra */``````

## Python3

``````# An iterative Java program to check if
# two linked lists are identical or not

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

def __init__( self ):

# Returns true if linked lists a and b
# are identical, otherwise false
def areIdentical( self , listb):
while (a ! = None and b ! = None ):
if (a.data ! = b.data):
return False

# If we reach here, then a and b
# are not null and their data is
# same, so move to next nodes
# in both lists
a = a. next
b = b. next

# If linked lists are identical, # then 'a' and 'b' must be null
# at this point.
return (a = = None and b = = None )

# UTILITY FUNCTIONS TO TEST fun1() and fun2()
# Given a reference (pointer to pointer) to the
# head of a list and an int, push a new node on
# the front of the list.

def push( self , new_data):

# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)

# 3. Make next of new Node as head

# 4. Move the head to point to new Node

# Driver Code

# The constructed linked lists are :
# llist1: 3->2->1
# llist2: 3->2->1
llist1.push( 1 )
llist1.push( 2 )
llist1.push( 3 )
llist2.push( 1 )
llist2.push( 2 )
llist2.push( 3 )

if (llist1.areIdentical(llist2) = = True ):
print ( "Identical " )
else :
print ( "Not identical " )

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

## C#

``````// An iterative C# program to
// check if two linked lists
// are identical or not
using System;

{

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

/* Returns true if linked lists
a and b are identical, otherwise false */
{
while (a != null && b != null )
{
if (a.data != b.data)
return false ;

/* If we reach here, then a and b are not null
and their data is same, so move to next nodes
in both lists */
a = a.next;
b = b.next;
}

// If linked lists are identical, // then 'a' and 'b' must
// be null at this point.
return (a == null && b == null );
}

/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */

void push( int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

/* 4. Move the head to point to new Node */
}

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

/* The constructed linked lists are :
llist1: 3->2->1
llist2: 3->2->1 */

llist1.push(1);
llist1.push(2);
llist1.push(3);

llist2.push(1);
llist2.push(2);
llist2.push(3);

if (llist1.areIdentical(llist2) == true )
Console.WriteLine( "Identical " );
else
Console.WriteLine( "Not identical " );
}
}

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

``Identical``

## C ++

``````// A recursive C++ function to check if two linked
// lists are identical or not
bool areIdentical(Node *a, Node *b)
{
// If both lists are empty
if (a == NULL && b == NULL)
return true ;

// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != NULL && b != NULL)
return (a->data == b->data) &&
areIdentical(a->next, b->next);

// If we reach here, then one of the lists
// is empty and other is not
return false ;
}

//This is code is contributed by rathbhupendra``````

## C

``````// A recursive C function to check if two linked
// lists are identical or not
bool areIdentical( struct Node *a, struct Node *b)
{
// If both lists are empty
if (a == NULL && b == NULL)
return true ;

// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != NULL && b != NULL)
return (a->data == b->data) &&
areIdentical(a->next, b->next);

// If we reach here, then one of the lists
// is empty and other is not
return false ;
}``````

## Java

``````// A recursive Java method to check if two linked
// lists are identical or not
boolean areIdenticalRecur(Node a, Node b)
{
// If both lists are empty
if (a == null && b == null )
return true ;

// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != null && b != null )
return (a.data == b.data) &&
areIdenticalRecur(a.next, b.next);

// If we reach here, then one of the lists
// is empty and other is not
return false ;
}

/* Returns true if linked lists a and b are identical, otherwise false */
{
}``````

## Python3

``````# A recursive Python3 function to check
# if two linked lists are identical or not
def areIdentical(a, b):

# If both lists are empty
if (a = = None and b = = None ):
return True

# If both lists are not empty, # then data of current nodes must match, # and same should be recursively true
# for rest of the nodes.
if (a ! = None and b ! = None ):
return ((a.data = = b.data) and
areIdentical(a. next , b. next ))

# If we reach here, then one of the lists
# is empty and other is not
return False

# This code is contributed by Princi Singh``````

## C#

``````// A recursive C# method to
// check if two linked lists
// are identical or not
bool areIdenticalRecur(Node a, Node b)
{
// If both lists are empty
if (a == null && b == null )
return true ;

// If both lists are not empty, then data of
// current nodes must match, and same should
// be recursively true for rest of the nodes.
if (a != null && b != null )
return (a.data == b.data) &&
areIdenticalRecur(a.next, b.next);

// If we reach here, then one of the lists
// is empty and other is not
return false ;
}

/* Returns true if linked lists
a and b are identical, otherwise false */ 