Skip to content

Instantly share code, notes, and snippets.

@rustyconover
Created May 7, 2015 15:59
Show Gist options
  • Save rustyconover/4ae51734af9be48717c3 to your computer and use it in GitHub Desktop.
Save rustyconover/4ae51734af9be48717c3 to your computer and use it in GitHub Desktop.
Find the first shared node between two linked lists
from operator import itemgetter
class ListNode:
def __init__(self, value):
self.value = value
# Append a node to this list node by setting the next property
def append(self, node):
self.next = node
# Build a list from an iterable
def build_list(elements):
head = None
current = None
for v in elements:
n = ListNode(v)
if head == None:
head = n
current = head
else:
current.append(n)
current = n
# Return both the head and the tail of the list
return (head, current)
# Get the length of the list by traversing it
def list_length(n):
count = 1;
try:
while n.next != None:
n = n.next
count += 1
except AttributeError:
return count
(first_list, first_tail) = build_list(range(1, 6))
(second_list, second_tail) = build_list(range(5, 7))
(shared_list, _) = build_list(range(100, 160))
first_tail.append(shared_list)
second_tail.append(shared_list)
# Get the length of each list an an array
lists_with_length = map(lambda l: (l, list_length(l)), [first_list, second_list])
# Sort the lists by length in descending order
lists_with_length.sort(key = itemgetter(1), reverse=True)
longer = lists_with_length[0][0]
shorter = lists_with_length[1][0]
diff = lists_with_length[0][1] - lists_with_length[1][1]
# Traverse the longer list the number of nodes by which it is longer
# than the shorter list.
while diff > 0:
longer = longer.next
diff -= 1
# Traverse both lists comparing the values.
try:
while 1:
if longer.value == shorter.value:
print("Shared node with value", shorter.value)
break
longer = longer.next
shorter = shorter.next
except AttributeError:
pass
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment