forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
/
rotate_to_the_right.py
156 lines (122 loc) · 4.02 KB
/
rotate_to_the_right.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
from __future__ import annotations
from dataclasses import dataclass
@dataclass
class Node:
data: int
next_node: Node | None = None
def print_linked_list(head: Node | None) -> None:
"""
Print the entire linked list iteratively.
This function prints the elements of a linked list separated by '->'.
Parameters:
head (Node | None): The head of the linked list to be printed,
or None if the linked list is empty.
>>> head = insert_node(None, 0)
>>> head = insert_node(head, 2)
>>> head = insert_node(head, 1)
>>> print_linked_list(head)
0->2->1
>>> head = insert_node(head, 4)
>>> head = insert_node(head, 5)
>>> print_linked_list(head)
0->2->1->4->5
"""
if head is None:
return
while head.next_node is not None:
print(head.data, end="->")
head = head.next_node
print(head.data)
def insert_node(head: Node | None, data: int) -> Node:
"""
Insert a new node at the end of a linked list and return the new head.
Parameters:
head (Node | None): The head of the linked list.
data (int): The data to be inserted into the new node.
Returns:
Node: The new head of the linked list.
>>> head = insert_node(None, 10)
>>> head = insert_node(head, 9)
>>> head = insert_node(head, 8)
>>> print_linked_list(head)
10->9->8
"""
new_node = Node(data)
# If the linked list is empty, the new_node becomes the head
if head is None:
return new_node
temp_node = head
while temp_node.next_node:
temp_node = temp_node.next_node
temp_node.next_node = new_node # type: ignore
return head
def rotate_to_the_right(head: Node, places: int) -> Node:
"""
Rotate a linked list to the right by places times.
Parameters:
head: The head of the linked list.
places: The number of places to rotate.
Returns:
Node: The head of the rotated linked list.
>>> rotate_to_the_right(None, places=1)
Traceback (most recent call last):
...
ValueError: The linked list is empty.
>>> head = insert_node(None, 1)
>>> rotate_to_the_right(head, places=1) == head
True
>>> head = insert_node(None, 1)
>>> head = insert_node(head, 2)
>>> head = insert_node(head, 3)
>>> head = insert_node(head, 4)
>>> head = insert_node(head, 5)
>>> new_head = rotate_to_the_right(head, places=2)
>>> print_linked_list(new_head)
4->5->1->2->3
"""
# Check if the list is empty or has only one element
if not head:
raise ValueError("The linked list is empty.")
if head.next_node is None:
return head
# Calculate the length of the linked list
length = 1
temp_node = head
while temp_node.next_node is not None:
length += 1
temp_node = temp_node.next_node
# Adjust the value of places to avoid places longer than the list.
places %= length
if places == 0:
return head # As no rotation is needed.
# Find the new head position after rotation.
new_head_index = length - places
# Traverse to the new head position
temp_node = head
for _ in range(new_head_index - 1):
assert temp_node.next_node
temp_node = temp_node.next_node
# Update pointers to perform rotation
assert temp_node.next_node
new_head = temp_node.next_node
temp_node.next_node = None
temp_node = new_head
while temp_node.next_node:
temp_node = temp_node.next_node
temp_node.next_node = head
assert new_head
return new_head
if __name__ == "__main__":
import doctest
doctest.testmod()
head = insert_node(None, 5)
head = insert_node(head, 1)
head = insert_node(head, 2)
head = insert_node(head, 4)
head = insert_node(head, 3)
print("Original list: ", end="")
print_linked_list(head)
places = 3
new_head = rotate_to_the_right(head, places)
print(f"After {places} iterations: ", end="")
print_linked_list(new_head)