cs1001.py , Tel Aviv University, Spring 2020

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: https://diveintopython3.net/special-method-names.html

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
Out[2]:
(1*x^0) + (1*x^1)
Out[2]:
(2*x^0) + (3*x^1) + (4*x^2)

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)
Out[3]:
1
Out[3]:
6
In [4]:
p = Polynomial([1,0,1])
q = Polynomial([1,0,1])
p == q
Out[4]:
False

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)
Out[5]:
False
Out[5]:
True
Out[5]:
True

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
Out[6]:
(3*x^0) + (4*x^1) + (4*x^2)
Out[6]:
(101*x^0) + (1*x^1)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-6-b1cbfd0c49d6> in <module>
     49 f+g
     50 f+100
---> 51 100+f

TypeError: unsupported operand type(s) for +: 'int' and 'Polynomial'

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
Out[7]:
(2*x^0) + (1*x^1)

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
Out[8]:
(-1*x^0) + (-1*x^1)

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
Out[9]:
(1*x^0) + (2*x^1) + (4*x^2)
Out[9]:
(1*x^0) + (3*x^1) + (4*x^2)

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
Out[10]:
(-1*x^1)
Out[10]:
(-1*x^0) + (-3*x^1) + (-4*x^2)

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
Out[4]:
[a,91843024] [b,91843088] [c,91842992] 

memory view

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
Out[5]:
[b,91843568] [a,91843664] 
A short summary of methods complexity of Linked lists vs. lists:
Method List Linked list
init $O(1)$ $O(1)$
init with $k$ items $O(k)$ $O(k)$
for the rest of the methods we assume that the structure contains $n$ items
add at start $O(n)$ $O(1)$
add at end $O(1)$ $O(n)$
$lst[k]$ (get the $k$th item) $O(1)$ $O(k)$
delete $lst[k]$ $O(n-k)$ $O(k)$

Reversing a linked list in $O(1)$ additional memory. See the code and demo here

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
Out[6]:
[a,91941296] [b,91941232] [c,91941200] 
Out[6]:
[c,91941200] [b,91941232] [a,91941296] 

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))
Out[32]:
[a,2582652271360] [b,2582652268728] [c,2582652271808] [d,2582652268840] 
Out[32]:
[e,2582652270800] [c,2582652271808] [d,2582652268840] 
Out[32]:
[d,2582652629344] 
True
False

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)
Out[13]:
[a,91940784] [b,91940624] [c,91940592] [d,91940272] 
Out[13]:
[e,91940432] [c,91940592] [d,91940272] 
Out[13]:
[d,1901584] 
True
False
advp
advp
[c,91940592] True
[c,91940592] True
[c,91940592] True

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)$