#!/usr/bin/env python
# coding: utf-8

# <h1><center>cs1001.py , Tel Aviv University, Spring 2020</center></h1>
# <img src="http://www.pngall.com/wp-content/uploads/2016/05/Python-Logo-PNG-Image-180x180.png" width=50/>

# # Recitation 9

# We discussed OOP and special methods that allow us to define operators in Python.
# Then, we saw an implementation of a Linked list data structure.
# 
# #### Takeaways:
# - OOP allows us to create classes at will and to define complex objects. Remember that the most important thing is to find a good inner representation of the object so that you will have an easy time working with it.
# 
# - Important properties of Linked lists: 
#     - Not stored continuously in memory.
#     - Allows for deletion and insertion after a __given__ element in $O(1)$ time.
#     - Accessing the $i$'th element takes $O(i)$ time.
#     - Search takes $O(n)$ time (no random access $\implies$ no $O(\log{n})$ search).
# 

# #### Code for printing several outputs in one cell (not part of the recitation):

# In[1]:


from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"


# ## OOP

# A link to special method names in python: <a href="https://diveintopython3.net/special-method-names.html">https://diveintopython3.net/special-method-names.html</a>

# ### Basic polynomial class
# 
# We represent a polynomial as a list of coefficients, where the $i$'th element in the list is the coefficient of $x^i$

# In[2]:


class Polynomial():
    def __init__(self, coeffs):
        self.coeffs = coeffs

        
        
    def __repr__(self):
        terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
                 str(k) + ")" \
                 for k in range(len(self.coeffs)) \
                 if self.coeffs[k] != 0]
        terms = "".join(terms)
        if terms == "":
            return "0"
        else:
            return terms[3:] #discard leftmost '+'

f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])

f
g


# #### Add degree and evaluate functions (these are special to class polynomial and are not part of Python's recognized functions)

# In[3]:


class Polynomial():
    def __init__(self, coeffs):
        self.coeffs = coeffs

    def __repr__(self):
        terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
                 str(k) + ")" \
                 for k in range(len(self.coeffs)) \
                 if self.coeffs[k] != 0]
        terms = "".join(terms)
        if terms == "":
            return "0"
        else:
            return terms[3:] #discard leftmost '+'

    def degree(self):
        return len(self.coeffs) - 1

    def evaluate(self, x):
        result = 0
        for i, c in enumerate(self.coeffs):
            result += c * pow(x, i)
        return result

f = Polynomial([1, 1])
f.degree()
f.evaluate(5)


# In[4]:


p = Polynomial([1,0,1])
q = Polynomial([1,0,1])
p == q


# #### Add \__eq\__ function for the '==' operator
# Without it, Python compares memory adderesses

# In[5]:


class Polynomial():
    def __init__(self, coeffs):
        self.coeffs = coeffs

    def __repr__(self):
        terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
                 str(k) + ")" \
                 for k in range(len(self.coeffs)) \
                 if self.coeffs[k] != 0]
        terms = "".join(terms)
        if terms == "":
            return "0"
        else:
            return terms[3:] #discard leftmost '+'

    def degree(self):
        return len(self.coeffs) - 1

    def evaluate(self, x):
        result = 0
        for i, c in enumerate(self.coeffs):
            result += c * pow(x, i)
        return result

    def __eq__(self, other):
        assert isinstance(other, Polynomial)  
        return self.coeffs == other.coeffs

f = Polynomial([1, 1])
f2 = Polynomial([1, 1])
g = Polynomial([2, 3, 4])

f == g
f == f2
f.__eq__(f2)


# #### Add the \__add\__ function for the '+' operator

# In[6]:


class Polynomial():
    def __init__(self, coeffs):
        self.coeffs = coeffs

    def __repr__(self):
        terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
                 str(k) + ")" \
                 for k in range(len(self.coeffs)) \
                 if self.coeffs[k] != 0]
        terms = "".join(terms)
        if terms == "":
            return "0"
        else:
            return terms[3:] #discard leftmost '+'

    def degree(self):
        return len(self.coeffs) - 1

    def evaluate(self, x):
        result = 0
        for i, c in enumerate(self.coeffs):
            result += c * pow(x, i)
        return result

    def __eq__(self, other):
        assert isinstance(other, Polynomial)  
        return self.coeffs == other.coeffs

    def __add__(self, other):
        assert isinstance(other, (Polynomial, int))  
        if isinstance(other, int):
            terms = [c for c in self.coeffs]
            terms[0] += other
            return Polynomial(terms)
        #else, other is a polynomial
        size = min(self.degree(), other.degree()) + 1
        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
        terms += self.coeffs[size : self.degree() + 1]
        terms += other.coeffs[size : other.degree() + 1]
        #remove leading zeros
        last = len(terms) - 1
        while last > 0 and terms[last] == 0:
            last -= 1
        return Polynomial(terms[:last+1])

f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])

f+g
f+100
100+f


# #### Add \__radd\__ function for right addition with int
# Since there is no support for addition with a Polynomial in the class int, python needs a definition of right addition for int in class Polynomial
# 
# When executing the command $f + 3$, python will first search for an \__add\__ method in class int that can support a second operand of type polynomial (self = int, other = polynomial).
# If such method does not exist, python will then search for an \__radd\__ method in class polynomial that can support a second operand of type int (self= polynomial, other = int).
# If such method does not exist, an exception is thrown.
# 
# Since + is commutative, then we set \__radd\__ to be identical to \__add\__
# 

# In[7]:


class Polynomial():
    def __init__(self, coeffs):
        self.coeffs = coeffs

    def __repr__(self):
        terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
                 str(k) + ")" \
                 for k in range(len(self.coeffs)) \
                 if self.coeffs[k] != 0]
        terms = "".join(terms)
        if terms == "":
            return "0"
        else:
            return terms[3:] #discard leftmost '+'

    def degree(self):
        return len(self.coeffs) - 1

    def evaluate(self, x):
        result = 0
        for i, c in enumerate(self.coeffs):
            result += c * pow(x, i)
        return result

    def __eq__(self, other):
        assert isinstance(other, Polynomial)  
        return self.coeffs == other.coeffs

    def __add__(self, other):
        assert isinstance(other, (Polynomial, int))  
        if isinstance(other, int):
            terms = [c for c in self.coeffs]
            terms[0] += other
            return Polynomial(terms)
        #else, other is a polynomial
        size = min(self.degree(), other.degree()) + 1
        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
        terms += self.coeffs[size : self.degree() + 1]
        terms += other.coeffs[size : other.degree() + 1]
        #remove leading zeros
        last = len(terms) - 1
        while last > 0 and terms[last] == 0:
            last -= 1
        return Polynomial(terms[:last+1])

    __radd__ = __add__ #to allow int+Polynomial

f = Polynomial([1, 1])
1 + f


# #### Add \__neg\__ function for unary minus (placing a '-' before a polynomial object)

# In[8]:


class Polynomial():
    def __init__(self, coeffs):
        self.coeffs = coeffs

    def __repr__(self):
        terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
                 str(k) + ")" \
                 for k in range(len(self.coeffs)) \
                 if self.coeffs[k] != 0]
        terms = "".join(terms)
        if terms == "":
            return "0"
        else:
            return terms[3:] #discard leftmost '+'

    def degree(self):
        return len(self.coeffs) - 1

    def evaluate(self, x):
        result = 0
        for i, c in enumerate(self.coeffs):
            result += c * pow(x, i)
        return result

    def __eq__(self, other):
        assert isinstance(other, Polynomial)  
        return self.coeffs == other.coeffs

    def __add__(self, other):
        assert isinstance(other, (Polynomial, int))  
        if isinstance(other, int):
            terms = [c for c in self.coeffs]
            terms[0] += other
            return Polynomial(terms)
        #else, other is a polynomial
        size = min(self.degree(), other.degree()) + 1
        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
        terms += self.coeffs[size : self.degree() + 1]
        terms += other.coeffs[size : other.degree() + 1]
        #remove leading zeros
        last = len(terms) - 1
        while last > 0 and terms[last] == 0:
            last -= 1
        return Polynomial(terms[:last+1])

    __radd__ = __add__ #to allow int+Polynomial
    
    def __neg__(self):
        return Polynomial([-co for co in self.coeffs])

f = Polynomial([1, 1])
-f


# #### Add \__sub\__  function to subtract one poly form another or an int from a poly
# Using the fact we already have \__neg\__ and \__add\__ we define $f-g = f + (-g)$

# In[9]:


class Polynomial():
    def __init__(self, coeffs):
        self.coeffs = coeffs

    def __repr__(self):
        terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
                 str(k) + ")" \
                 for k in range(len(self.coeffs)) \
                 if self.coeffs[k] != 0]
        terms = "".join(terms)
        if terms == "":
            return "0"
        else:
            return terms[3:] #discard leftmost '+'

    def degree(self):
        return len(self.coeffs) - 1

    def evaluate(self, x):
        result = 0
        for i, c in enumerate(self.coeffs):
            result += c * pow(x, i)
        return result

    def __eq__(self, other):
        assert isinstance(other, Polynomial)  
        return self.coeffs == other.coeffs

    def __add__(self, other):
        assert isinstance(other, (Polynomial, int))  
        if isinstance(other, int):
            terms = [c for c in self.coeffs]
            terms[0] += other
            return Polynomial(terms)
        #else, other is a polynomial
        size = min(self.degree(), other.degree()) + 1
        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
        terms += self.coeffs[size : self.degree() + 1]
        terms += other.coeffs[size : other.degree() + 1]
        #remove leading zeros
        last = len(terms) - 1
        while last > 0 and terms[last] == 0:
            last -= 1
        return Polynomial(terms[:last+1])

    __radd__ = __add__ #to allow int+Polynomial
    
    def __neg__(self):
        return Polynomial([-co for co in self.coeffs])
    
    def __sub__(self, other):
        assert isinstance(other, (int, Polynomial))  
        return (self + (-other))
    
f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])

g - f
g - 1


# #### Add \__rsub\__ function for right subtraction
# Using the fact we already have \__neg\__ and \__sub\__ we define $f-g = -(g-f)$
# 
# since oprator \- is not commutative, then we cannot set \__rsub\__ to be identical to \__sub\__
# 
# Note that the following implementation of \__rsub\__ is promlematic, because it will keep calling itself (infinitely)
# 
#     def __rsub__(self, other):
#         return other-self #PROBLEMATIC!
# 
# 
# 

# In[10]:


class Polynomial():
    def __init__(self, coeffs):
        self.coeffs = coeffs

    def __repr__(self):
        terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
                 str(k) + ")" \
                 for k in range(len(self.coeffs)) \
                 if self.coeffs[k] != 0]
        terms = "".join(terms)
        if terms == "":
            return "0"
        else:
            return terms[3:] #discard leftmost '+'

    def degree(self):
        return len(self.coeffs) - 1

    def evaluate(self, x):
        result = 0
        for i, c in enumerate(self.coeffs):
            result += c * pow(x, i)
        return result

    def __eq__(self, other):
        assert isinstance(other, Polynomial)  
        return self.coeffs == other.coeffs

    def __add__(self, other):
        assert isinstance(other, (Polynomial, int))  
        if isinstance(other, int):
            terms = [c for c in self.coeffs]
            terms[0] += other
            return Polynomial(terms)
        #else, other is a polynomial
        size = min(self.degree(), other.degree()) + 1
        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
        terms += self.coeffs[size : self.degree() + 1]
        terms += other.coeffs[size : other.degree() + 1]
        #remove leading zeros
        last = len(terms) - 1
        while last > 0 and terms[last] == 0:
            last -= 1
        return Polynomial(terms[:last+1])

    __radd__ = __add__ #to allow int+Polynomial

    def __neg__(self):
        return Polynomial([-co for co in self.coeffs])

    def __sub__(self, other):
        assert isinstance(other, (int, Polynomial))  
        return (self + (-other))

    #__rsub__ = __sub__ #not what we want...

    def __rsub__(self, other):
        # other - self
        return -(self - other) #why not just other-self ?

f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])

1 - f
1 - g


# ## Linked Lists

# A linked list is a linear data structure (i.e. - nodes can be accessed one after the other). The list is composed of nodes, where each node contains a value and a "pointer" to the next node in the list.
# 
# Linked lists support operations such as insertion, deletion, search and many more.

# In[3]:


class Node():
    def __init__(self, val):
        self.value = val
        self.next = None
        
    def __repr__(self):
        #return "[" + str(self.value) + "," + str(id(self.next))+ "]"
        
        #for today's recitation, we print the id of self instead of self.next
        return "[" + str(self.value) + "," + str(id(self))+ "]"



class Linked_list():

    def __init__(self, seq=None):
        self.next = None
        self.len = 0
        if seq != None:
            for x in seq[::-1]:
                self.add_at_start(x)
            

    def __repr__(self):
       out = ""
       p = self.next
       while p != None:
           out += str(p) + " " #str envokes __repr__ of class Node
           p = p.next
       return out

            
    def __len__(self):
        ''' called when using Python's len() '''
        return self.len
            
            
    def add_at_start(self, val):
        ''' add node with value val at the list head '''
        p = self
        tmp = p.next
        p.next = Node(val)
        p.next.next = tmp
        self.len += 1
    
    def add_at_end(self, val):
        ''' add node with value val at the list tail '''
        p = self
        while (p.next != None):
            p = p.next
        p.next = Node(val)
        self.len += 1
            
        
    def insert(self, loc, val):
        ''' add node with value val after location 0<=loc<len of the list '''
        assert 0 <= loc < len(self)
        p = self
        for i in range(0, loc):
            p = p.next
        tmp = p.next
        p.next = Node(val)
        p.next.next = tmp
        self.len += 1
        
          
    def __getitem__(self, loc):
        ''' called when using L[i] for reading
            return node at location 0<=loc<len '''
        assert 0 <= loc < len(self)
        p = self.next
        for i in range(0, loc):
            p = p.next
        return p

    def __setitem__(self, loc, val):
        ''' called when using L[loc]=val for writing
            assigns val to node at location 0<=loc<len '''
        assert 0 <= loc < len(self)
        p = self.next
        for i in range(0, loc):
            p = p.next
        p.value = val
        return None

    
    def find(self, val):
        ''' find (first) node with value val in list '''
        p = self.next
        # loc = 0     # in case we want to return the location
        while p != None:
            if p.value == val:
                return p
            else:
                p = p.next
                #loc=loc+1   # in case we want to return the location
        return None

    def delete(self, loc):
        ''' delete element at location 0<=loc<len '''
        assert 0 <= loc < len(self)
        p = self
        for i in range(0, loc):
            p = p.next
        # p is the element BEFORE loc
        p.next = p.next.next
        self.len -= 1
 
    
    def insert_ordered(self, val):
        ''' assume self is an ordered list,
            insert Node with val in order '''
        p = self
        q = self.next
        while q != None and q.value < val:
            p = q
            q = q.next
        newNode = Node(val)
        p.next = newNode
        newNode.next = q
        self.len += 1

    def find_ordered(self, val):
        ''' assume self is an ordered list,
            find Node with value val '''
        p = self.next
        while p != None and p.value < val:
            p = p.next
        if p != None and p.value == val: 
            return p
        else:
            return None


# Converting a string to a list

# In[4]:


L= Linked_list("abc")
L


# memory view

# <img src="linked_lst_mem.PNG">

# Adding elements one by one. Try using Python tutor. 

# In[5]:


l = Linked_list()
l.add_at_start("a")
l.add_at_start("b")
l


# ##### A short summary of methods complexity of Linked lists vs. lists:

# <table width=550 align="left">
#         <tr>
#             <td> <b>Method</b></td>
#             <td> <b>List</b></td>
#             <td> <b>Linked list</b></td>
#     </tr>
#     <tr>
#             <td> init</td>
#             <td> $O(1)$</td>
#             <td> $O(1)$</td>
#     </tr>
#     <tr> 
#         <td> init with $k$ items</td>
#         <td> $O(k)$</td>
#         <td> $O(k)$</td>
#     </tr>
#     <tr> 
#         <td colspan="3"><b>for the rest of the methods we assume that the structure contains $n$ items</b></td>
#     </tr>
#     <tr> 
#         <td> add at start</td>
#         <td> $O(n)$</td>
#         <td> $O(1)$</td>
#     </tr>
#     <tr> 
#         <td> add at end</td>
#         <td> $O(1)$</td>
#         <td> $O(n)$</td>
#     </tr>
#     <tr> 
#         <td> $lst[k]$ (get the $k$th item)</td>
#         <td> $O(1)$</td>
#         <td> $O(k)$</td>
#     </tr>
#     <tr> 
#         <td> delete $lst[k]$</td>
#         <td> $O(n-k)$</td>
#         <td> $O(k)$</td>
#     </tr>
# </table>

# Reversing a linked list in $O(1)$ additional memory. 
# See the code and demo <a href="http://tau-cs1001-py.wdfiles.com/local--files/recitation-logs-2017b/m_09_reverse_list.pdf">here</a>

# In[6]:


class Node():
    def __init__(self, val):
        self.value = val
        self.next = None
        
    def __repr__(self):
        #return "[" + str(self.value) + "," + str(id(self.next))+ "]"
        
        #for today's recitation, we print the id of self instead of self.next
        return "[" + str(self.value) + "," + str(id(self))+ "]"


class Linked_list():

    def __init__(self, seq=None):
        self.next = None
        self.len = 0
        if seq != None:
            for x in seq[::-1]:
                self.add_at_start(x)
            

    def __repr__(self):
       out = ""
       p = self.next
       while p != None:
           out += str(p) + " " #str envokes __repr__ of class Node
           p = p.next
       return out

            
    def __len__(self):
        ''' called when using Python's len() '''
        return self.len
            
            
    def add_at_start(self, val):
        ''' add node with value val at the list head '''
        p = self
        tmp = p.next
        p.next = Node(val)
        p.next.next = tmp
        self.len += 1
    
    def add_at_end(self, val):
        ''' add node with value val at the list tail '''
        p = self
        while (p.next != None):
            p = p.next
        p.next = Node(val)
        self.len += 1
            
        
    def insert(self, loc, val):
        ''' add node with value val after location 0<=loc<len of the list '''
        assert 0 <= loc < len(self)
        p = self
        for i in range(0, loc):
            p = p.next
        tmp = p.next
        p.next = Node(val)
        p.next.next = tmp
        self.len += 1
        
          
    def __getitem__(self, loc):
        ''' called when using L[i] for reading
            return node at location 0<=loc<len '''
        assert 0 <= loc < len(self)
        p = self.next
        for i in range(0, loc):
            p = p.next
        return p

    def __setitem__(self, loc, val):
        ''' called when using L[loc]=val for writing
            assigns val to node at location 0<=loc<len '''
        assert 0 <= loc < len(self)
        p = self.next
        for i in range(0, loc):
            p = p.next
        p.value = val
        return None

    
    def find(self, val):
        ''' find (first) node with value val in list '''
        p = self.next
        # loc = 0     # in case we want to return the location
        while p != None:
            if p.value == val:
                return p
            else:
                p = p.next
                #loc=loc+1   # in case we want to return the location
        return None

    def delete(self, loc):
        ''' delete element at location 0<=loc<len '''
        assert 0 <= loc < len(self)
        p = self
        for i in range(0, loc):
            p = p.next
        # p is the element BEFORE loc
        p.next = p.next.next
        self.len -= 1
 
    
    def insert_ordered(self, val):
        ''' assume self is an ordered list,
            insert Node with val in order '''
        p = self
        q = self.next
        while q != None and q.value < val:
            p = q
            q = q.next
        newNode = Node(val)
        p.next = newNode
        newNode.next = q
        self.len += 1

    def find_ordered(self, val):
        ''' assume self is an ordered list,
            find Node with value val '''
        p = self.next
        while p != None and p.value < val:
            p = p.next
        if p != None and p.value == val: 
            return p
        else:
            return None

    def reverse(self):
        prev = None
        curr = self.next
        while curr != None:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
        self.next = prev
        
ll = Linked_list("abc")
ll
ll.reverse()
ll


# Exam question (2018, Spring Semester)
# 
# Let $L,K$ be two linked lists of length $n,m$ respectively. We say that the **lists merge** if there exists a node that is on both lists.
# 
# I.e. - there exists a node $q$ in $L$ and $p$ in $K$ such that $q ~is~ p == True$. In such a case we call $p$ a **joint node**.
# 
# Write a function $are\_merged$ that gets two linked lists as an input and returns True iff the lists merge.
# 
# The main idea - two linked lists merge if and only if their last node (their tail) is the same node.
# 

# In[32]:


def are_merged(L, K):
    node_l = L.next
    node_k = K.next
    while node_l.next != None:
        node_l = node_l.next
    while node_k.next != None:
        node_k = node_k.next
    return node_k is node_l
    
    #Here is an equivalent solution with a shorter code:
    #last_node_l = L[len(L)-1]
    #last_node_k = K[len(K)-1]
    #return last_node_l is last_node_k

L = Linked_list("abcd")
L

K = Linked_list()
K.next = L.next.next.next
# Manually define the length of K
K.len = 2
K.add_at_start("e")
K

M = Linked_list()
M.add_at_start("d")
M

print(are_merged(L,K))
print(are_merged(L,M))



# ### Time and space analysis
# 
# Space: Saving a pointer to two nodes can be done in $O(1)$ memory
# Time: Each node in the lists is read exactly once and all operations run in time $O(1)$ so runtime is $O(n+m)$

# Next, write a function $find\_shared$ that gets two merged linked lists as an input and returns the first joint node of the lists.
# 
# Analyze its running time and space complexity.

# In[13]:


def find_shared_1(L, K):
    id_set = set()
    p = L.next
    while p != None:
        id_set.add(id(p))
        p = p.next
    q = K.next
    while q != None:
        if id(q) in id_set:
            return q
        q = q.next
    return None # should not reach here since L, K have joint items


def find_shared_2(L, K):
    n = len(L)
    m = len(K)
    p = L.next
    q = K.next
    for i in range(max(0, n-m)):
        print('advp')
        p = p.next
    for i in range(max(0, m-n)):
        print('advq')
        q = q.next
    while p != None:
        if p is q:
            return p
        p = p.next
        q = q.next
    return None # Should never get here

def find_shared_3(L, K):
    p = L.next
    q = K.next
    while p != None and q != None:
        if p is q:
            return p
        p = p.next
        q = q.next
        if p == None:
            p = K.next
        if q == None:
            q = L.next
    return None # must end before, since L, K have joint items    

L = Linked_list("abcd")
L

K = Linked_list()
K.next = L.next.next.next
# Save the first joint node
x = K.next
K.len = 2
K.add_at_start("e")
K

M = Linked_list()
M.add_at_start("d")
M

print(are_merged(L,K))
print(are_merged(L,M))



print(find_shared_1(L,K), find_shared_1(L,K) == x)
print(find_shared_2(L,K), find_shared_2(L,K) == x)
print(find_shared_3(L,K), find_shared_3(L,K) == x)


# For the analysis assume wlog that $n \geq m$:
# * For find_shared_1:
#     * Space: Saving all of the node ids from $L$ in a set: $O(n)$, saving one or two node pointers at a time is $O(1)$
#     * Time: All lookups in the set run in $O(1)$ on average, apart from that each node in $K,L$ is read exactly once - $O(n)$ on average
# * For find_shared_2:
#     * Space: Saving $n,m$ and an index for the for loop: $O(\log n)$, saving one or two node pointers at a time is $O(1)$
#     * Time: First two for loops and the while loop traverse each node in $K,L$ exactly once - $O(n)$
# * For find_shared_3:
#     * Space: Saving one or two node pointers throughout the while loop is $O(1)$
#     * Time: Pointer p will first traverse the $n$ nodes of L and then the $m$ nodes of K. Pointer $q$ will first traverse the $m$ nodes of K and then the $n$ nodes of L. Suppose that the joint part is of length $w$, then both pointers will reach it after $n+m-w$ steps. Since all operations in the while loop run in $O(1)$ time, the overall running time is $O(n)$
#