Solution to the interview problem Reverse Linked List [+ ВИДЕО]
The video provides a more detailed explanation of each solution.
Statement of the problem
Link to the task: https://leetcode.com/problems/reverse-linked-list
The pointer is given head to the beginning of a singly linked list, you need to unwrap the list and return the unwrap list.
1. Solution using an array
One way to solve this problem is to use an array to store all the nodes in the list. We can then iterate through the array in reverse order, setting next pointers at each node.
Description of the solution
Initializing an array: We create an empty array
nodeswhich we will use to store all the nodes of the list.Filling the array: After going through the entire list, we add each node to the array. The resulting array is
nodeswill contain all nodes in the order they appear in the list.Rebinding pointers: Walking through the array from left to right, starting with the second element, we set for each node
nextpointer to the previous element in the array.Zeroing out the next pointer of the first element: Since the first element in the array (which was the last node of the list) must become the last node of the reversed list, its pointer
nextmust be installed inNone.Return the new head: At the end we return the last element of the array as a new one
headinverted list.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None: # Если список пуст, возвращаем None
return None
nodes = [] # Массив для хранения узлов
while head:
nodes.append(head) # Добавляем узел в массив
head = head.next # Переходим к следующему узлу
for i in range(1, len(nodes)):
node = nodes[i]
# Устанавливаем указатель next
node.next = nodes[i - 1]
# Устанавливаем None для последнего элемента в перевернутом списке
nodes[0].next = None
return nodes[-1] # Возвращаем новый headComplexity of the algorithm
• By time: O(n), where n is the number of elements in the list.
• From memory: O(n) since we store all the elements of the list into an array.
Visualization
Let's look at the visualization of the algorithm using the example of a list 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Initializing an empty nodes array:
• We start with an empty array: nodes = [].
Filling an array with list nodes:
• We go through the original list and add each node to the array:
• After the first step:
nodes = [1](where 1 is a reference to the list node with value 1)• After the second step:
nodes = [1, 2]• After the third step:
nodes = [1, 2, 3]• After the fourth step:
nodes = [1, 2, 3, 4]• After step five:
nodes = [1, 2, 3, 4, 5]The nodes array now contains references to all the nodes in the list in their original order.
Rebinding next pointers:
• Now we go through the array, starting from the second index, and for each node we set it
nextpointer to the previous node in the array.• For node 2 (the second element of the array):
nodes[1].next = nodes[0]New list:
2 <-> 1(the first node still refers to the secondso the connection goes both ways, cyclical connection)• For node 3 (the third element of the array):
nodes[2].next = nodes[1]New list: 3 -> 2 <-> 1
• For node 4 (the fourth element of the array):
nodes[3].next = nodes[2]New list:
4 -> 3 -> 2 <-> 1• For node 5 (the fifth element of the array):
nodes[4].next = nodes[3]New list:
5 -> 4 -> 3 -> 2 <-> 1At this point, all nodes, starting from the second one, point to the previous nodes in the new order.
Zeroing out the next pointer for the first node of the array:
• Since the first element of the array is now the last one in the new list, its next pointer must be
None.nodes[0].next = NoneNow the first node (former 1 -> NULL) becomes the last:
5 -> 4 -> 3 -> 2 -> 1 -> NULL.Return the new head of the list:
• The last element of the array
nodes[-1]which contains a node with the value5now becomes newheadlist.As a result, the original list
1 -> 2 -> 3 -> 4 -> 5 -> NULLturns into an inverted list5 -> 4 -> 3 -> 2 -> 1 -> NULL.
2. Solution using the two pointer method
Approach
This algorithm does not require any additional memory other than a few pointers, making it more efficient than the array-based method. The idea is to gradually unfold the connections between nodes by traversing the list once.
Algorithm
Initialization of the prev pointer:
We start with the prev pointer, which is initially equal toNone. This pointer will be used to store the previous node in the reversed list.Navigate through the list:
We walk the list, changing each node's next pointer to point to the previous node (
prev). To do this, we perform the following steps in the cycle:• Store a pointer to the next node (
tmp = head.next) so as not to lose it after changinghead.next.• Change the current pointer
nextnodeheadso that it points toprev.• We move
prevto the current node (prev = head).• We move
headto the next node (head = tmp).Return the new head:
After completing the list traversal
prevwill point to the last node of the original list, which will now becomeheadinverted list.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None # Инициализация указателя на предыдущий узел
while head:
tmp = head.next # Сохраняем указатель на следующий узел
head.next = prev # Разворачиваем текущий узел
prev = head # Смещаем указатель prev на текущий узел
head = tmp # Переходим к следующему узлу
return prev # Возвращаем новый head спискаComplexity of the algorithm
• By time: O(n), where n is the number of elements in the list.
• From memory: O(1), since we only use two pointers.
Visualization
Let's look at the original list 1 -> 2 -> 3 -> 4 -> 5 -> NULL.
Initialization:
prev = None,head = 1.First step of the cycle:
•
tmp = 2(save the next node)•
head.next = None(expand the pointer1 -> NULL)•
prev = 1,head = 2.State: 1 -> NULL, 2 -> 3 -> 4 -> 5 -> NULL.
Second step of the cycle:
•
tmp = 3(save the next node)•
head.next = 1(expand the pointer2 -> 1)•
prev = 2,head = 3.State:
2 -> 1 -> NULL,3 -> 4 -> 5 -> NULL.Let's repeat until the end:
After completing all the steps, we get an inverted list:
5 -> 4 -> 3 -> 2 -> 1 -> NULL.
