# Linked List Interview Challenges for Major Tech Companies: Amazon, Facebook, Apple, Microsoft

*Question 1 : Remove Duplicates*

Write a function to remove duplicates from an unsorted linked list. Input 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 Output 1 -> 2 -> 3 -> 4 -> 5

```
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
def __str__(self):
temp_node = self.head
result = ''
while temp_node is not None:
result += str(node.value)
if temp_node.next is not None:
result += ' -> '
temp_node = temp_node.next
return result
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.length += 1
def remove_duplicates(ll):
# TODO
```

**Answer :** We will assign a pointer that will traverse through the linked list. The we will check if the next node is same as the pointer node or not. If yes, we update the pointer nodes next reference to next node's next node. If not, we simply traverse. At the end, we make a prev node and update the tail to the prev node.

```
from linkedlist import LinkedList
def remove_duplicates(ll):
# TODO
if ll.head is None:
return
current_node = ll.self #will be used to traverse the list.
prev_node = None #used to keep track of the node before current_node
while current_node:
runner = current_node
while runner.next:
if runner.next.value == current_node.value :
runner.next = runner.next.next
else:
runner = runner.next
prev_node = current_node
current_node = current_node.next
ll.tail = prev_node
```

`runner = current_node`

- Inside the while loop,`runner`

is set to the`current_node`

.`runner`

will be used to look ahead in the list for duplicates.`while runner.next:`

- This is a nested while loop that runs as long as`runner.next`

is not`None`

. This loop is used to check for duplicates of`current_node`

's value in the remaining list.`if runner.next.value == current_node.value:`

- This is a condition to check if the next value in the list (after`runner`

) is the same as the value of`current_node`

.`prev_node = current_node`

- After we have checked all the remaining list for duplicates of`current_node`

, we set`prev_node`

to`current_node`

`current_node = current_node.next`

- We move`current_node`

one step forward in the list.`ll.tail = prev_node`

- After the outer while loop ends (meaning we have traversed the entire list),`prev_node`

is the last node in the list. We set`ll.tail`

to`prev_node`

, effectively updating the tail of the LinkedList.

**The time and space complexity**

Time : Since the function has a nested loop that, in the worst case, runs for N^2 iterations, the overall time complexity is O(N^2), where N is the number of nodes in the LinkedList.

Space : O(1)

*Question 2 : Return nth to last*

If n is 3, we need to return the 3rd element to the last node. The logic here is, we make two pointer and set them to head. Our code will take two params - list, and n.

```
def nthToLast(li, n):
pointer1 = li.head
pointer2 = li.head
for i in range(n):
if pointer2 is None:
return None
pointer2 = pointer2.next
while pointer2:
pointer1 = pointer1.next
pointer2 = pointer2.next
return pointer 1
```

Time complexity: O(N), Space complexity : O(1)

*Question 3 : Partition*

Write a code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

```
from LinkedList import LinkedList
def partition(li,x):
current_node = li.head
li.tail = li.head
while current_node:
nextNode = current_node.next
if current_node.value <= x:
current_node.next = li.head
li.head = current_node
else:
li.tail.next = current_node
li.tail = current_node
current_node = current_node.next
if li.tail.next is not None:
li.tail.next = None
```

Time complexity: O(N), Space complexity : O(1)

*Question 4 : Sum Lists*

you have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, 1's digit is at the head of the list. Write a function that adds two numbers and returns the sum as a linked list.

Code:

```
from LinkedList mport LinkedList
def sumList(liA, liB):
n1 = liA.head
n2 = liB.head
carry = 0
li = LinkedList()
while n1 or n2:
result = carry
if n1:
result += n1.value
n1 = n1.next
if n2:
result += n2.value
n2 = n2.next
li.add(int(result % 10))
carry = result / 10
return li
```

Time complexity: O(N), Space complexity : O(N), because here we are creating another LinkedList.