Singly Linked List- Remove node with value "k", with O(1) space complexity-CodePudding

So this was a problem on CodeSignal, and due to the space complexity constraint, a recursive algorithm must be used. The following C code passes all the tests, but i'm unable to figure out what's happening in the nested else if block. Here's the code.

//
// Definition for singly-linked list:
// typedef struct list_##name {
//   type value;
//   struct list_##name *next;
// } list_##name;
//
// list_##name *alloc_list_##name(type v) {
//   list_##name *l = calloc(1, sizeof(list_##name));
//   l->value = v;
//   return l;
// }
//
list_integer * solution(list_integer * l, int k) {
    
    if(l != NULL){ 
        if(l->value == k){
            return solution(l->next, k);
        } else {
            l->next = solution(l->next, k);
        }
    }
    return l;
}

And this is the same function in python

# Singly-linked lists are already defined with this interface:
# class ListNode(object):
#   def __init__(self, x):
#     self.value = x
#     self.next = None
#
def solution(l, k):
    if l:
        if l.value == k:
            return solution(l.next, k)
        else:
            l.next = solution(l.next, k)
    return l

Can anyone please explain how the recursion part works? Thank you.

CodePudding user response：

mutation migraine

Because you are reassigning l.next = ..., it's surprisingly difficult to illustrate and talk about the computational process. But let's give it a try -

If I have 1 -> 2 -> 3 -> 4 -> None and I want to remove 3 -

The first node contains value = 1 and next = 2 -> 3 -> 4 -> none. 1 does not match k, so

l.next = solution(l.next, k)

Now we are solving for 2 -> 3 -> 4 -> None and that will be set to l.next.

value = 2 and next = 3 -> 4 -> None. 2 does not match k, so

l.next = solution(l.next, k)

Now we are solving for 3 -> 4 -> None and that will be set to l.next.

value = 3 and next = 4 -> None. 3 does match k, so

return l.next

So the 2 node, next is set to 4 -> None, which becomes 2 -> 4 -> Nnoe

And for the 1 node, next is set to the 2 node, so 1 -> 2 -> 4 -> None

The 3 is removed!

history lesson

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignment, and other side effects. Rather than modifying the list in place, A functional solution would create a new list. When a pure function is used, any function call be be substituted for its value without changing the meaning of the program -

def remove(l, k):
  if not l:
    return l
  elif l.value == k:
    return l.next
  else:
    return ListNode(l.value, remove(l.next, k))

Because no mutations are being used, the process is extremely easy to communicate now -

mylist = ListNode(1, ListNode(2, ListNode(3, ListNode(4, None))))
newList = remove(myList, 3)
newList = remove(ListNode(1, ListNode(2, ListNode(3, ListNode(4, None)))), 3)
newList = ListNode(1, remove(ListNode(2, ListNode(3, ListNode(4, None))), 3))
newList = ListNode(1, ListNode(2, remove(ListNode(3, ListNode(4, None)), 3)))
newList = ListNode(1, ListNode(2, ListNode(4, None)))