Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

communitycreator
linkedlist

How to find the merge point for two linked lists

Dhruv Sharma

Overview

A linked list is a collection of nodes. Each node contains data and a pointer to the next node.

A linked list is preferred over other data structures like arrays because it has a dynamic size and it's easier to insert and delete elements/nodes.

Creating a linked list

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def print_ll(self):
        temp = self.head
        while temp:
            print(str(temp.data))
            temp = temp.next
  
    def insert(self, data):
        node = Node(data)
        if not self.head:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
  
l1 = SinglyLinkedList()
l1val = [1,2,3,4,5]

for i in l1val:
    l1.insert(i)
    
l1.print_ll()
Creating a linked list

Explanation

In a linked list, the head attribute refers to the first node of a list. All the functions used in the list are added in the SinglyLinkedList class.

Node class is used to create a new node, each node has a data attribute and a pointer attribute to the next node which initially points to a null.

Understanding the Problem

Consider two linked lists that will meet at some point. The head nodes of both lists are given pointers to find the node where the two lists merge.

Creating the merge for the linked lists
Creating the merge for the linked lists

Example

In the above example, the two lists merge at Node 4, which is the result of the function.

Solution

In the program below, we use the merge_point() function to find the data of the node where both the lists merge.

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert(self, data):
        node = SinglyLinkedListNode(data)
        if not self.head:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node

def merge_point(head1, head2):
    data = []
    while head1 != None:
        data.append(head1)
        head1 = head1.next
    while head2 != None:
        if head2 in data:
            return (head2.data)
        head2 = head2.next

l1 = SinglyLinkedList()
l1val = [1,2,3,4,5]
l1_count = 5
for i in l1val:
    l1.insert(i)

l2 = SinglyLinkedList()
l2val = [9,2]
l2_count = 2
for i in l2val:
    l2.insert(i)

ptr1 = l1.head;
ptr2 = l2.head;

for i in range(l1_count):
    if i < 3:
        ptr1 = ptr1.next
        
for i in range(l2_count):
    if i != l2_count-1:
        ptr2 = ptr2.next
ptr2.next = ptr1

print(merge_point(l1.head, l2.head))
Finding merge point of two linked lists

Explanation

We follow the steps below to run the merge_point() function:

Lines 21–23: Traverse the first linked list and add all the nodes in a list called data

Lines 24–25: Check if any node exists in the data list to traverse the second linked list.

Lines 25–26: Use an exit condition to return the data of the node which exist in the data list.

RELATED TAGS

communitycreator
linkedlist
RELATED COURSES

View all Courses

Keep Exploring