Scribd
Upload
18 views3 pages

LinkedList Merge Problem Python

The document presents a Python implementation for merging and appending linked lists with a shared tail. It includes a ListNode class and a NumberChainUtils class with methods to find the merge point, calculate lengths before merging, clone lists, and append tails. A unittest is provided to validate the functionality with a specific test case.

Uploaded by

HRITHIK SINGH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views3 pages

LinkedList Merge Problem Python

The document presents a Python implementation for merging and appending linked lists with a shared tail. It includes a ListNode class and a NumberChainUtils class with methods to find the merge point, calculate lengths before merging, clone lists, and append tails. A unittest is provided to validate the functionality with a specific test case.

Uploaded by

HRITHIK SINGH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Linked List Merge and Append Problem - Python Implementation

list_node.py

class ListNode:
def __init__(self, val):
[Link] = val
[Link] = None

number_chain_utils.py

from list_node import ListNode

class NumberChainUtils:

@staticmethod
def get_merge_point(headA, headB):
a, b = headA, headB
while a != b:
a = b if a is None else [Link]
b = headA if b is None else [Link]
return a

@staticmethod
def get_length_before_merge(head, merge):
length = 0
curr = head
while curr and curr != merge:
length += 1
curr = [Link]
return length

@staticmethod
def clone_before_merge(head, merge):
dummy = ListNode(0)
tail = dummy
curr = head
while curr != merge:
[Link] = ListNode([Link])
tail = [Link]
curr = [Link]
return [Link]

@staticmethod
def append_tail(head, addition):
if not head:
return addition
curr = head
while [Link]:
curr = [Link]
[Link] = addition
Linked List Merge and Append Problem - Python Implementation

return head

@staticmethod
def solve(chain1, chain2):
merge = NumberChainUtils.get_merge_point(chain1, chain2)
if not merge:
return None

len1 = NumberChainUtils.get_length_before_merge(chain1, merge)


len2 = NumberChainUtils.get_length_before_merge(chain2, merge)

if len1 < len2:


cloned = NumberChainUtils.clone_before_merge(chain1, merge)
return NumberChainUtils.append_tail(chain2, cloned)
else:
cloned = NumberChainUtils.clone_before_merge(chain2, merge)
return NumberChainUtils.append_tail(chain1, cloned)

test_number_chain_utils.py

import unittest
from list_node import ListNode
from number_chain_utils import NumberChainUtils

class TestNumberChainUtils([Link]):

def list_to_array(self, head):


result = []
while head:
[Link]([Link])
head = [Link]
return result

def test_merge_and_append(self):
# Shared tail: 8 -> 10
shared = ListNode(8)
[Link] = ListNode(10)

# List 1: 1 -> 2 -> 3 -> 8 -> 10


a = ListNode(1)
[Link] = ListNode(2)
[Link] = ListNode(3)
[Link] = shared

# List 2: 4 -> 5 -> 8 -> 10


b = ListNode(4)
[Link] = ListNode(5)
[Link] = shared
Linked List Merge and Append Problem - Python Implementation

result = [Link](a, b)
expected = [1, 2, 3, 8, 10, 4, 5]
[Link](self.list_to_array(result), expected)

if __name__ == '__main__':
[Link]()

You might also like