Python Program to Find the first Common Element between the 2 given Linked Lists

«
»

This is a Python program to find the first element of the first linked list that is common to both the lists.

Problem Description

The program creates two linked lists using data items input from the user and determines the first element in the first linked list that is in both the lists.

Problem Solution

1. Create a class Node with instance variables data and next.
2. Create a class LinkedList with instance variables head and last_node.
3. The variable head points to the first element in the linked list while last_node points to the last.
4. Define methods append and display inside the class LinkedList to append data and display the linked list respectively.
5. Define a function first_common which takes two linked lists as arguments.
6. The function first_common returns the first element in the first linked list that is common to both the linked lists using two nested loops.
7. Create two instances of LinkedList and append data to it.
8. Find the common element and display the result.

advertisement
Program/Source Code

Here is the source code of a Python program to find the first common element in two linked lists.

class Node:
    def __init__(self, data):
       self.data = data
       self.next = None
 
 
class LinkedList:
    def __init__(self):
        self.head = None
        self.last_node = None
 
    def append(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
 
 
def first_common(llist1, llist2):
    current1 = llist1.head
    while current1:
        data = current1.data
        current2 = llist2.head
        while current2:
            if data == current2.data:
                return data
            current2 = current2.next
        current1 = current1.next
    return None
 
 
llist1 = LinkedList()
llist2 = LinkedList()
 
data_list = input('Please enter the elements in the first linked list: ').split()
for data in data_list:
    llist1.append(int(data))
 
data_list = input('Please enter the elements in the second linked list: ').split()
for data in data_list:
    llist2.append(int(data))
 
common = first_common(llist1, llist2)
 
if common:
    print('The element that appears first in the first linked list that'
          ' is common to both is {}.'.format(common))
else:
    print('The two lists have no common elements.')
Program Explanation

1. Two instances of LinkedList are created.
2. The user is prompted to enter the data items for the two lists.
3. The function first_common is called to find the common element.
4. The result is then displayed.

advertisement
advertisement
Runtime Test Cases
Case 1:
Please enter the elements in the first linked list: 4 5 1 3 10
Please enter the elements in the second linked list: 8 3 40 1
The element that appears first in the first linked list that is common to both is 1.
 
Case 2:
Please enter the elements in the first linked list: 1 4 5
Please enter the elements in the second linked list: 3 10
The two lists have no common elements.
 
Case 3:
Please enter the elements in the first linked list: 6 8 9
Please enter the elements in the second linked list: 7 10 6 4 9 8
The element that appears first in the first linked list that is common to both is 6.

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

advertisement

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter