Linked list

Solution:.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
a = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")

a.next = b
b.next = c
c.next = d

def print_list_iterative(head):
    current = head
    while current is not None:
        print(current.val)
        current = current.next
print_list_iterative(a)

def print_list_recursive(head):
    if head is None:
        return
    print(head.val)
    print_list_recursive(head.next)
print_list_recursive(a)

Problem:
Write a function, linked_list_values, that takes in the head of a linked list as an argument. The function should return a list containing all values of the nodes in the linked list.
Hey. This is our first linked list problem, so you should be liberal with watching the Approach and Walkthrough. Be productive! -AZ

# test_00:
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")

a.next = b
b.next = c
c.next = d

# a -> b -> c -> d
linked_list_values(a) # -> [ 'a', 'b', 'c', 'd' ]

Solution

Iterative

def linked_list_values(head):
    values = []
    current = head
    while current is not None:
        values.append(current.val)
        current = current.next
    return values

Recursive

def linked_list_values(head):
    values = []
    _linked_list_values(head, values)
    return values

def _linked_list_values(head, values):
    if head is None:
        return
    values.append(head.val)
    _linked_list_values(head.next, values)

Problem:
Write a function, sum_list, that takes in the head of a linked list containing numbers as an argument.
The function should return the total sum of all values in the linked list.

# test_00:
a = Node(2)
b = Node(8)
c = Node(3)
d = Node(-1)
e = Node(7)

a.next = b
b.next = c
c.next = d
d.next = e

# 2 -> 8 -> 3 -> -1 -> 7
sum_list(a) # 19

Solution

Iterative

def sum_list(head):
    total_sum = 0
    current = head
    while current is not None:
        total_sum += current.val
        current = current.next
    return total_sum

Recursive

def sum_list(head):
    if head is None:
        return 0
    return head.val + sum_list(head.next)

Problem:
Write a function, linked_list_find, that takes in the head of a linked list and a target value. The function should return a boolean indicating whether or not the linked list contains the target.

# test_00:
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")

a.next = b
b.next = c
c.next = d

# a -> b -> c -> d

linked_list_find(a, "c") # True

Solution
The key to solve this problem is thinking like this 🤔. You are traversing through linked list & at any point of time, if you come across head.val == target, return True & make sure that True is carried forward back to the parent calls.
If you did not find True until end of the linked list, then return False & make sure that True is carried forward back to the parent calls.

Iterative

def linked_list_find(head, target):
    current = head
    while current is not None:
        if current.val == target:
            return True
        current = current.next
    return False

Recursive

def linked_list_find(head, target):
    if head is None:
        return False
    if head.val == target:
        return True
    return linked_list_find(head.next, target)

Problem:
Write a function, get_node_value, that takes in the head of a linked list and an index. The function should return the value of the linked list at the specified index.
If there is no node at the given index, then return None.

# test_00:
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")

a.next = b
b.next = c
c.next = d

# a -> b -> c -> d
get_node_value(a, 2) # 'c'

Solution
Tip:
Most of the Linked List problems will ask to do the work in place. So, the solution revolves around modifying the pointers, not creating new Linked List. Aware of this fact.

Iterative

def get_node_value(head, index):
    count = 0
    current = head
    while current is not None:
        if count == index:
            return current.val
        current = current.next
        count += 1
    return None

Recursive

def get_node_value(head, index):
    if head is None:
        return None
    if index == 0:
        return head.val
    return get_node_value(head.next, index - 1)

Problem:
Write a function, reverse_list, that takes in the head of a linked list as an argument. The function should reverse the order of the nodes in the linked list in-place and return the new head of the reversed linked list.

# test_00:
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")

a.next = b
b.next = c
c.next = d
d.next = e
e.next = f

# a -> b -> c -> d -> e -> f
reverse_list(a) # f -> e -> d -> c -> b -> a

Solution
— How to think 🤔
— This is how the linked list looks.

Observe that the question says, Linked List has to be reversed in place. So, the whole idea is to reverse the pointer of each node. Let’s see how the picture looks like when we reverse the pointer of first node.

We are done with the first node. Let’s move the head to next node & do the same process. Then the picture looks like below & This process has to be continued until the head is None.

Let’s solve this problem iteratively to get some sense & then will move to recursive way.

Iterative

def reverse_list(head):
    prev = None  # see the picture 1
    while head is not None:
        # upcoming 2 lines are to make the head.next to point towards prev
        temp = head.next  # before reversing the pointer of node,
        # first save the next node pointer to an temp variable.
        # If you just reverse the pointer without doing this,
        # you dont know what is next node. Got it?
        head.next = prev

        # moving to the next node
        prev = head
        head = temp
    return prev

Recursive

def reverse_list(head, prev=None):
    # base case
    if head is None:
        return prev
    # recursive step
    # reassign the pointer of head to prev node
    temp = head.next
    head.next = prev
    # move the head to next node
    prev = head
    head = temp
    return reverse_list(head, prev)

Problem:
Write a function, zipper_lists, that takes in the head of two linked lists as arguments. The function should zipper the two lists together into single linked list by alternating nodes. If one of the linked lists is longer than the other, the resulting list should terminate with the remaining nodes. The function should return the head of the zippered linked list.
Do this in-place, by mutating the original Nodes.
You may assume that both input lists are non-empty.

# test_00:
a = Node("a")
b = Node("b")
c = Node("c")
a.next = b
b.next = c
# a -> b -> c

x = Node("x")
y = Node("y")
z = Node("z")
x.next = y
y.next = z
# x -> y -> z

zipper_lists(a, x)
# a -> x -> b -> y -> c -> z

Solution

Iterative

def zipper_lists(head_1, head_2):
    tail = head_1  # output LL, which already includes one node from LL 1
    # Let’s take 2 pointers, to identify the current location
    # when we are working on these lists.
    current_1 = head_1.next  # LL 1
    current_2 = head_2  # LL 2

    count = 0  # if this count is even, we will take a node from LL 2
    # if this count is odd, we will take a node from LL 1
    while current_1 is not None and current_2 is not None:
        if count % 2 == 0:
            tail.next = current_2
            current_2 = current_2.next
        else:
            tail.next = current_1
            current_1 = current_1.next
        tail = tail.next
        count += 1

    if current_1 is not None:
        tail.next = current_1
    if current_2 is not None:
        tail.next = current_2

    return head_1

Recursive

def zipper_lists(head_1, head_2):
    if head_1 is None and head_2 is None:
        return None
    if head_1 is None:
        return head_2
    if head_2 is None:
        return head_1
    next_1 = head_1.next
    next_2 = head_2.next
    head_1.next = head_2
    head_2.next = zipper_lists(next_1, next_2)
    return head_1

Problem:
Write a function, merge_lists, that takes in the head of two sorted linked lists as arguments. The function should merge the two lists together into single sorted linked list. The function should return the head of the merged linked list.
Do this in-place, by mutating the original Nodes.
You may assume that both input lists are non-empty and contain increasing sorted numbers.

# test_00:
a = Node(5)
b = Node(7)
c = Node(10)
d = Node(12)
e = Node(20)
f = Node(28)
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
# 5 -> 7 -> 10 -> 12 -> 20 -> 28

q = Node(6)
r = Node(8)
s = Node(9)
t = Node(25)
q.next = r
r.next = s
s.next = t
# 6 -> 8 -> 9 -> 25

merge_lists(a, q)
# 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 12 -> 20 -> 25 -> 28 

Solution

Iterative

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

def merge_lists(head_1, head_2):
    # Let's create an dummy node.
    # This is the node which we will evolve during our solution.
    # So, eventually it becomes our output Linked List.
    dummy_head = Node(None)

    # Initially, we point our tail to dummy node.
    # This tail, we will keep pointing to other nodes
    # in Linked List 1 & 2 while we work our way through the problem.
    # That's how we will arrive at the
    # output Linked List.
    tail = dummy_head

    # We take two pointers to track out current location on
    # Linked List 1 & 2, while we are working our way to the final solution.
    current_1 = head_1
    current_2 = head_2

    # This while loop runs until, any one of the Linked List becomes empty.
    while current_1 is not None and current_2 is not None:
        # This is the block of code where we are doing the core logic
        # of working our way towards the output list.
        if current_1.val < current_2.val:
            tail.next = current_1
            current_1 = current_1.next
        else:
            tail.next = current_2
            current_2 = current_2.next
        tail = tail.next
    # When any one of the Linked List becomes empty,
    # will just attach the left over other Linked List to our output
    # Linked List.
    if current_1 is not None:
        tail.next = current_1
    if current_2 is not None:
        tail.next = current_2

    return dummy_head.next

Recursive

def merge_lists(head_1, head_2):
    # Base cases -- They are here to stop the recursion,
    # whenever one of the Linked List becomes empty.
    if head_1 is None and head_2 is None:
        return None
    if head_1 is None:
        return head_2
    if head_2 is None:
        return head_1

    # Recursive step
    if head_1.val < head_2.val:
        next_1 = head_1.next
        head_1.next = merge_lists(next_1, head_2)
        return head_1
    else:
        next_2 = head_2.next
        head_2.next = merge_lists(head_1, next_2)
        return head_2

Problem:
Write a function, is_univalue_list, that takes in the head of a linked list as an argument. The function should return a boolean indicating whether or not the linked list contains exactly one unique value.
You may assume that the input list is non-empty.

# test_00:
a = Node(7)
b = Node(7)
c = Node(7)

a.next = b
b.next = c

# 7 -> 7 -> 7
is_univalue_list(a) # True 

Solution

Iterative

def is_univalue_list(head):
    current = head
    while current is not None:
        if current.val != head.val:
            return False
        current = current.next
    return True

Recursive

def is_univalue_list(head, prev_val=None):
    if head is None:
        return True
    if prev_val is None or head.val == prev_val:
        return is_univalue_list(head.next, head.val)
    else:
        return False

Problem:
Write a function, longest_streak, that takes in the head of a linked list as an argument. The function should return the length of the longest consecutive streak of the same value within the list.

# test_00:
a = Node(5)
b = Node(5)
c = Node(7)
d = Node(7)
e = Node(7)
f = Node(6)

a.next = b
b.next = c
c.next = d
d.next = e
e.next = f

# 5 -> 5 -> 7 -> 7 -> 7 -> 6
longest_streak(a) # 3

Solution

Iterative

def longest_streak(head):
    max_streak = 0
    current_streak = 0
    prev_val = None

    current_node = head
    while current_node is not None:
        if current_node.val == prev_val:
            current_streak += 1
        else:
            current_streak = 1
        prev_val = current_node.val
        if current_streak > max_streak:
            max_streak = current_streak
        current_node = current_node.next
    return max_streak

Problem:
Write a function, remove_node, that takes in the head of a linked list and a target value as arguments. The function should delete the node containing the target value from the linked list and return the head of the resulting linked list. If the target appears multiple times in the linked list, only remove the first instance of the target in the list.
Do this in-place.
You may assume that the input list is non-empty.
You may assume that the input list contains the target.

# test_00:
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")

a.next = b
b.next = c
c.next = d
d.next = e
e.next = f

# a -> b -> c -> d -> e -> f
remove_node(a, "c")
# a -> b -> d -> e -> f

Solution
— Let’s have 2 pointers prev & current, and will start traversing through the Linked List.
— Why you need 2 pointers?
Assume that, you are traversing through the Linked List & on the process, you found current.val == value of the node which needs to be removed.
Then, because of the reason you have 2 pointers named prev & current, you can easily do prev.next = current.next,
which removes the current node from Linked List.

Iterative

def remove_node(head, target_val):
    # Edge case: what if the node which needs to be removed is head node?
    # Our regular logic which we wrote is side the while loop will fail,
    # in this case. Hence, that case needs to be dealt as an edge case.
    if head.val == target_val:
        return head.next

    current = head
    prev = None
    while current is not None:
        if current.val == target_val:
            prev.next = current.next
            break
        prev = current
        current = current.next
    return head

Recursive

def remove_node(head, target_val):
    # Base case
    if head is None:
        return None

    # Remember that we saw an edge case in iterative code.
    # This base case is to deal with that edge case.
    if head.val == target_val:
        return head.next

    head.next = remove_node(head.next, target_val)
    return head

Problem:
Write a function, insert_node, that takes in the head of a linked list, a value, and an index. The function should insert a new node with the value into the list at the specified index. Consider the head of the linked list as index 0. The function should return the head of the resulting linked list.
Do this in-place.
You may assume that the input list is non-empty and the index is not greater than the length of the input list.

# test_00:
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")

a.next = b
b.next = c
c.next = d

# a -> b -> c -> d
insert_node(a, 'x', 2)
# a -> b -> x -> c -> d

Solution
— Let’s have 2 pointers prev & current, and will start traversing through the Linked List.
— Why you need 2 pointers?
Assume that, you are traversing through the Linked List & on the process, you found current.val == value of the node which needs to be removed.
Then, because of the reason you have 2 pointers named prev & current, you can easily do prev.next = current.next,
which removes the current node from Linked List.

Iterative

def insert_node(head, value, index):
    # This is an edge case. First read the remaining code.
    # At the end, read this.
    # Even when you are coding, do it the same way. First write the solution
    # Then think about the base case.
    if index == 0:
        new_head = Node(value)
        new_head.next = head
        return new_head
    # These 2 variables are necessary to keep track on which node you are on &
    # what's the corresponding index.
    count = 0
    current = head

    # These 2 lines are classic way of looping through each node of Linked List
    # while current is not None:
    #   <what_ever_logic_you_want_to_execute>
    #   current = current.next
    while current is not None:
        if count == index - 1:
            temp = current.next
            current.next = Node(value)
            current.next.next = temp

        count += 1
        current = current.next
    return head

Recursive

# If you observe the iterative approach, we took 2 variables named
# "current" & "count", They are to track the node at which we are
# currently at is index - 1 ?
# Because, that's where we have to insert the new node.
# In iterative approach, we kept increasing the count inside the while loop.
# Here, once you increase the count,
# the variable needs to be passed to recursive fn.
# That's why we have count parameter.
def insert_node(head, value, index, count=0):
    # This is edge case, which is same to same as that of iterative approach.
    if index == 0:
        new_head = Node(value)
        new_head.next = head
        return new_head

    # Base case -- While you are traversing the Linked List,
    # you have reached the end but did not found the index yet.
    # Which means, nothing you can do. Just return None.
    if head is None:
        return None

    # Recursive step
    # The core logic is once again same to same as that of iterative.
    if count == index - 1:
        temp = head.next
        head.next = Node(value)
        head.next.next = temp
        return

    insert_node(head.next, value, index, count + 1)
    return head