Python/data_structures/linked_list/reverse_k_group.py at master · PreciousJac0b/Python · GitHub

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
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
next_node: Node|None=None


classLinkedList:
def__init__(self, ints: Iterable[int]) ->None:
self.head: Node|None=None
foriinints:
self.append(i)

def__iter__(self) ->Iterator[int]:
"""
 >>> ints = []
 >>> list(LinkedList(ints)) == ints
 True
 >>> ints = tuple(range(5))
 >>> tuple(LinkedList(ints)) == ints
 True
 """
node=self.head
whilenode:
yieldnode.data
node=node.next_node

def__len__(self) ->int:
"""
 >>> for i in range(3):
 ... len(LinkedList(range(i))) == i
 True
 True
 True
 >>> len(LinkedList("abcdefgh"))
 8
 """
returnsum(1for_inself)

def__str__(self) ->str:
"""
 >>> str(LinkedList([]))
 ''
 >>> str(LinkedList(range(5)))
 '0 -> 1 -> 2 -> 3 -> 4'
 """
return" -> ".join([str(node) fornodeinself])

defappend(self, data: int) ->None:
"""
 >>> ll = LinkedList([1, 2])
 >>> tuple(ll)
 (1, 2)
 >>> ll.append(3)
 >>> tuple(ll)
 (1, 2, 3)
 >>> ll.append(4)
 >>> tuple(ll)
 (1, 2, 3, 4)
 >>> len(ll)
 4
 """
ifnotself.head:
self.head=Node(data)
return
node=self.head
whilenode.next_node:
node=node.next_node
node.next_node=Node(data)

defreverse_k_nodes(self, group_size: int) ->None:
"""
 reverse nodes within groups of size k
 >>> ll = LinkedList([1, 2, 3, 4, 5])
 >>> ll.reverse_k_nodes(2)
 >>> tuple(ll)
 (2, 1, 4, 3, 5)
 >>> str(ll)
 '2 -> 1 -> 4 -> 3 -> 5'
 """
ifself.headisNoneorself.head.next_nodeisNone:
return

length=len(self)
dummy_head=Node(0)
dummy_head.next_node=self.head
previous_node=dummy_head

whilelength>=group_size:
current_node=previous_node.next_node
assertcurrent_node
next_node=current_node.next_node
for_inrange(1, group_size):
assertnext_node, current_node
current_node.next_node=next_node.next_node
assertprevious_node
next_node.next_node=previous_node.next_node
previous_node.next_node=next_node
next_node=current_node.next_node
previous_node=current_node
length-=group_size
self.head=dummy_head.next_node


if__name__=="__main__":
importdoctest

doctest.testmod()
ll=LinkedList([1, 2, 3, 4, 5])
print(f"Original Linked List: {ll}")
k=2
ll.reverse_k_nodes(k)
print(f"After reversing groups of size {k}: {ll}")
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
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
next_node: Node|None=None


classLinkedList:
def__init__(self, ints: Iterable[int]) ->None:
self.head: Node|None=None
foriinints:
self.append(i)

def__iter__(self) ->Iterator[int]:
"""
 >>> ints = []
 >>> list(LinkedList(ints)) == ints
 True
 >>> ints = tuple(range(5))
 >>> tuple(LinkedList(ints)) == ints
 True
 """
node=self.head
whilenode:
yieldnode.data
node=node.next_node

def__len__(self) ->int:
"""
 >>> for i in range(3):
 ... len(LinkedList(range(i))) == i
 True
 True
 True
 >>> len(LinkedList("abcdefgh"))
 8
 """
returnsum(1for_inself)

def__str__(self) ->str:
"""
 >>> str(LinkedList([]))
 ''
 >>> str(LinkedList(range(5)))
 '0 -> 1 -> 2 -> 3 -> 4'
 """
return" -> ".join([str(node) fornodeinself])

defappend(self, data: int) ->None:
"""
 >>> ll = LinkedList([1, 2])
 >>> tuple(ll)
 (1, 2)
 >>> ll.append(3)
 >>> tuple(ll)
 (1, 2, 3)
 >>> ll.append(4)
 >>> tuple(ll)
 (1, 2, 3, 4)
 >>> len(ll)
 4
 """
ifnotself.head:
self.head=Node(data)
return
node=self.head
whilenode.next_node:
node=node.next_node
node.next_node=Node(data)

defreverse_k_nodes(self, group_size: int) ->None:
"""
 reverse nodes within groups of size k
 >>> ll = LinkedList([1, 2, 3, 4, 5])
 >>> ll.reverse_k_nodes(2)
 >>> tuple(ll)
 (2, 1, 4, 3, 5)
 >>> str(ll)
 '2 -> 1 -> 4 -> 3 -> 5'
 """
ifself.headisNoneorself.head.next_nodeisNone:
return

length=len(self)
dummy_head=Node(0)
dummy_head.next_node=self.head
previous_node=dummy_head

whilelength>=group_size:
current_node=previous_node.next_node
assertcurrent_node
next_node=current_node.next_node
for_inrange(1, group_size):
assertnext_node, current_node
current_node.next_node=next_node.next_node
assertprevious_node
next_node.next_node=previous_node.next_node
previous_node.next_node=next_node
next_node=current_node.next_node
previous_node=current_node
length-=group_size
self.head=dummy_head.next_node


if__name__=="__main__":
importdoctest

doctest.testmod()
ll=LinkedList([1, 2, 3, 4, 5])
print(f"Original Linked List: {ll}")
k=2
ll.reverse_k_nodes(k)
print(f"After reversing groups of size {k}: {ll}")
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
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
next_node: Node|None=None


classLinkedList:
def__init__(self, ints: Iterable[int]) ->None:
self.head: Node|None=None
foriinints:
self.append(i)

def__iter__(self) ->Iterator[int]:
"""
 >>> ints = []
 >>> list(LinkedList(ints)) == ints
 True
 >>> ints = tuple(range(5))
 >>> tuple(LinkedList(ints)) == ints
 True
 """
node=self.head
whilenode:
yieldnode.data
node=node.next_node

def__len__(self) ->int:
"""
 >>> for i in range(3):
 ... len(LinkedList(range(i))) == i
 True
 True
 True
 >>> len(LinkedList("abcdefgh"))
 8
 """
returnsum(1for_inself)

def__str__(self) ->str:
"""
 >>> str(LinkedList([]))
 ''
 >>> str(LinkedList(range(5)))
 '0 -> 1 -> 2 -> 3 -> 4'
 """
return" -> ".join([str(node) fornodeinself])

defappend(self, data: int) ->None:
"""
 >>> ll = LinkedList([1, 2])
 >>> tuple(ll)
 (1, 2)
 >>> ll.append(3)
 >>> tuple(ll)
 (1, 2, 3)
 >>> ll.append(4)
 >>> tuple(ll)
 (1, 2, 3, 4)
 >>> len(ll)
 4
 """
ifnotself.head:
self.head=Node(data)
return
node=self.head
whilenode.next_node:
node=node.next_node
node.next_node=Node(data)

defreverse_k_nodes(self, group_size: int) ->None:
"""
 reverse nodes within groups of size k
 >>> ll = LinkedList([1, 2, 3, 4, 5])
 >>> ll.reverse_k_nodes(2)
 >>> tuple(ll)
 (2, 1, 4, 3, 5)
 >>> str(ll)
 '2 -> 1 -> 4 -> 3 -> 5'
 """
ifself.headisNoneorself.head.next_nodeisNone:
return

length=len(self)
dummy_head=Node(0)
dummy_head.next_node=self.head
previous_node=dummy_head

whilelength>=group_size:
current_node=previous_node.next_node
assertcurrent_node
next_node=current_node.next_node
for_inrange(1, group_size):
assertnext_node, current_node
current_node.next_node=next_node.next_node
assertprevious_node
next_node.next_node=previous_node.next_node
previous_node.next_node=next_node
next_node=current_node.next_node
previous_node=current_node
length-=group_size
self.head=dummy_head.next_node


if__name__=="__main__":
importdoctest

doctest.testmod()
ll=LinkedList([1, 2, 3, 4, 5])
print(f"Original Linked List: {ll}")
k=2
ll.reverse_k_nodes(k)
print(f"After reversing groups of size {k}: {ll}")
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
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
next_node: Node|None=None


classLinkedList:
def__init__(self, ints: Iterable[int]) ->None:
self.head: Node|None=None
foriinints:
self.append(i)

def__iter__(self) ->Iterator[int]:
"""
 >>> ints = []
 >>> list(LinkedList(ints)) == ints
 True
 >>> ints = tuple(range(5))
 >>> tuple(LinkedList(ints)) == ints
 True
 """
node=self.head
whilenode:
yieldnode.data
node=node.next_node

def__len__(self) ->int:
"""
 >>> for i in range(3):
 ... len(LinkedList(range(i))) == i
 True
 True
 True
 >>> len(LinkedList("abcdefgh"))
 8
 """
returnsum(1for_inself)

def__str__(self) ->str:
"""
 >>> str(LinkedList([]))
 ''
 >>> str(LinkedList(range(5)))
 '0 -> 1 -> 2 -> 3 -> 4'
 """
return" -> ".join([str(node) fornodeinself])

defappend(self, data: int) ->None:
"""
 >>> ll = LinkedList([1, 2])
 >>> tuple(ll)
 (1, 2)
 >>> ll.append(3)
 >>> tuple(ll)
 (1, 2, 3)
 >>> ll.append(4)
 >>> tuple(ll)
 (1, 2, 3, 4)
 >>> len(ll)
 4
 """
ifnotself.head:
self.head=Node(data)
return
node=self.head
whilenode.next_node:
node=node.next_node
node.next_node=Node(data)

defreverse_k_nodes(self, group_size: int) ->None:
"""
 reverse nodes within groups of size k
 >>> ll = LinkedList([1, 2, 3, 4, 5])
 >>> ll.reverse_k_nodes(2)
 >>> tuple(ll)
 (2, 1, 4, 3, 5)
 >>> str(ll)
 '2 -> 1 -> 4 -> 3 -> 5'
 """
ifself.headisNoneorself.head.next_nodeisNone:
return

length=len(self)
dummy_head=Node(0)
dummy_head.next_node=self.head
previous_node=dummy_head

whilelength>=group_size:
current_node=previous_node.next_node
assertcurrent_node
next_node=current_node.next_node
for_inrange(1, group_size):
assertnext_node, current_node
current_node.next_node=next_node.next_node
assertprevious_node
next_node.next_node=previous_node.next_node
previous_node.next_node=next_node
next_node=current_node.next_node
previous_node=current_node
length-=group_size
self.head=dummy_head.next_node


if__name__=="__main__":
importdoctest

doctest.testmod()
ll=LinkedList([1, 2, 3, 4, 5])
print(f"Original Linked List: {ll}")
k=2
ll.reverse_k_nodes(k)
print(f"After reversing groups of size {k}: {ll}")
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
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
next_node: Node|None=None


classLinkedList:
def__init__(self, ints: Iterable[int]) ->None:
self.head: Node|None=None
foriinints:
self.append(i)

def__iter__(self) ->Iterator[int]:
"""
 >>> ints = []
 >>> list(LinkedList(ints)) == ints
 True
 >>> ints = tuple(range(5))
 >>> tuple(LinkedList(ints)) == ints
 True
 """
node=self.head
whilenode:
yieldnode.data
node=node.next_node

def__len__(self) ->int:
"""
 >>> for i in range(3):
 ... len(LinkedList(range(i))) == i
 True
 True
 True
 >>> len(LinkedList("abcdefgh"))
 8
 """
returnsum(1for_inself)

def__str__(self) ->str:
"""
 >>> str(LinkedList([]))
 ''
 >>> str(LinkedList(range(5)))
 '0 -> 1 -> 2 -> 3 -> 4'
 """
return" -> ".join([str(node) fornodeinself])

defappend(self, data: int) ->None:
"""
 >>> ll = LinkedList([1, 2])
 >>> tuple(ll)
 (1, 2)
 >>> ll.append(3)
 >>> tuple(ll)
 (1, 2, 3)
 >>> ll.append(4)
 >>> tuple(ll)
 (1, 2, 3, 4)
 >>> len(ll)
 4
 """
ifnotself.head:
self.head=Node(data)
return
node=self.head
whilenode.next_node:
node=node.next_node
node.next_node=Node(data)

defreverse_k_nodes(self, group_size: int) ->None:
"""
 reverse nodes within groups of size k
 >>> ll = LinkedList([1, 2, 3, 4, 5])
 >>> ll.reverse_k_nodes(2)
 >>> tuple(ll)
 (2, 1, 4, 3, 5)
 >>> str(ll)
 '2 -> 1 -> 4 -> 3 -> 5'
 """
ifself.headisNoneorself.head.next_nodeisNone:
return

length=len(self)
dummy_head=Node(0)
dummy_head.next_node=self.head
previous_node=dummy_head

whilelength>=group_size:
current_node=previous_node.next_node
assertcurrent_node
next_node=current_node.next_node
for_inrange(1, group_size):
assertnext_node, current_node
current_node.next_node=next_node.next_node
assertprevious_node
next_node.next_node=previous_node.next_node
previous_node.next_node=next_node
next_node=current_node.next_node
previous_node=current_node
length-=group_size
self.head=dummy_head.next_node


if__name__=="__main__":
importdoctest

doctest.testmod()
ll=LinkedList([1, 2, 3, 4, 5])
print(f"Original Linked List: {ll}")
k=2
ll.reverse_k_nodes(k)
print(f"After reversing groups of size {k}: {ll}")
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
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
next_node: Node|None=None


classLinkedList:
def__init__(self, ints: Iterable[int]) ->None:
self.head: Node|None=None
foriinints:
self.append(i)

def__iter__(self) ->Iterator[int]:
"""
 >>> ints = []
 >>> list(LinkedList(ints)) == ints
 True
 >>> ints = tuple(range(5))
 >>> tuple(LinkedList(ints)) == ints
 True
 """
node=self.head
whilenode:
yieldnode.data
node=node.next_node

def__len__(self) ->int:
"""
 >>> for i in range(3):
 ... len(LinkedList(range(i))) == i
 True
 True
 True
 >>> len(LinkedList("abcdefgh"))
 8
 """
returnsum(1for_inself)

def__str__(self) ->str:
"""
 >>> str(LinkedList([]))
 ''
 >>> str(LinkedList(range(5)))
 '0 -> 1 -> 2 -> 3 -> 4'
 """
return" -> ".join([str(node) fornodeinself])

defappend(self, data: int) ->None:
"""
 >>> ll = LinkedList([1, 2])
 >>> tuple(ll)
 (1, 2)
 >>> ll.append(3)
 >>> tuple(ll)
 (1, 2, 3)
 >>> ll.append(4)
 >>> tuple(ll)
 (1, 2, 3, 4)
 >>> len(ll)
 4
 """
ifnotself.head:
self.head=Node(data)
return
node=self.head
whilenode.next_node:
node=node.next_node
node.next_node=Node(data)

defreverse_k_nodes(self, group_size: int) ->None:
"""
 reverse nodes within groups of size k
 >>> ll = LinkedList([1, 2, 3, 4, 5])
 >>> ll.reverse_k_nodes(2)
 >>> tuple(ll)
 (2, 1, 4, 3, 5)
 >>> str(ll)
 '2 -> 1 -> 4 -> 3 -> 5'
 """
ifself.headisNoneorself.head.next_nodeisNone:
return

length=len(self)
dummy_head=Node(0)
dummy_head.next_node=self.head
previous_node=dummy_head

whilelength>=group_size:
current_node=previous_node.next_node
assertcurrent_node
next_node=current_node.next_node
for_inrange(1, group_size):
assertnext_node, current_node
current_node.next_node=next_node.next_node
assertprevious_node
next_node.next_node=previous_node.next_node
previous_node.next_node=next_node
next_node=current_node.next_node
previous_node=current_node
length-=group_size
self.head=dummy_head.next_node


if__name__=="__main__":
importdoctest

doctest.testmod()
ll=LinkedList([1, 2, 3, 4, 5])
print(f"Original Linked List: {ll}")
k=2
ll.reverse_k_nodes(k)
print(f"After reversing groups of size {k}: {ll}")
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
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
next_node: Node|None=None


classLinkedList:
def__init__(self, ints: Iterable[int]) ->None:
self.head: Node|None=None
foriinints:
self.append(i)

def__iter__(self) ->Iterator[int]:
"""
 >>> ints = []
 >>> list(LinkedList(ints)) == ints
 True
 >>> ints = tuple(range(5))
 >>> tuple(LinkedList(ints)) == ints
 True
 """
node=self.head
whilenode:
yieldnode.data
node=node.next_node

def__len__(self) ->int:
"""
 >>> for i in range(3):
 ... len(LinkedList(range(i))) == i
 True
 True
 True
 >>> len(LinkedList("abcdefgh"))
 8
 """
returnsum(1for_inself)

def__str__(self) ->str:
"""
 >>> str(LinkedList([]))
 ''
 >>> str(LinkedList(range(5)))
 '0 -> 1 -> 2 -> 3 -> 4'
 """
return" -> ".join([str(node) fornodeinself])

defappend(self, data: int) ->None:
"""
 >>> ll = LinkedList([1, 2])
 >>> tuple(ll)
 (1, 2)
 >>> ll.append(3)
 >>> tuple(ll)
 (1, 2, 3)
 >>> ll.append(4)
 >>> tuple(ll)
 (1, 2, 3, 4)
 >>> len(ll)
 4
 """
ifnotself.head:
self.head=Node(data)
return
node=self.head
whilenode.next_node:
node=node.next_node
node.next_node=Node(data)

defreverse_k_nodes(self, group_size: int) ->None:
"""
 reverse nodes within groups of size k
 >>> ll = LinkedList([1, 2, 3, 4, 5])
 >>> ll.reverse_k_nodes(2)
 >>> tuple(ll)
 (2, 1, 4, 3, 5)
 >>> str(ll)
 '2 -> 1 -> 4 -> 3 -> 5'
 """
ifself.headisNoneorself.head.next_nodeisNone:
return

length=len(self)
dummy_head=Node(0)
dummy_head.next_node=self.head
previous_node=dummy_head

whilelength>=group_size:
current_node=previous_node.next_node
assertcurrent_node
next_node=current_node.next_node
for_inrange(1, group_size):
assertnext_node, current_node
current_node.next_node=next_node.next_node
assertprevious_node
next_node.next_node=previous_node.next_node
previous_node.next_node=next_node
next_node=current_node.next_node
previous_node=current_node
length-=group_size
self.head=dummy_head.next_node


if__name__=="__main__":
importdoctest

doctest.testmod()
ll=LinkedList([1, 2, 3, 4, 5])
print(f"Original Linked List: {ll}")
k=2
ll.reverse_k_nodes(k)
print(f"After reversing groups of size {k}: {ll}")
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
from __future__ importannotations

fromcollections.abcimportIterable, Iterator
fromdataclassesimportdataclass


@dataclass
classNode:
data: int
next_node: Node|None=None


classLinkedList:
def__init__(self, ints: Iterable[int]) ->None:
self.head: Node|None=None
foriinints:
self.append(i)

def__iter__(self) ->Iterator[int]:
"""
 >>> ints = []
 >>> list(LinkedList(ints)) == ints
 True
 >>> ints = tuple(range(5))
 >>> tuple(LinkedList(ints)) == ints
 True
 """
node=self.head
whilenode:
yieldnode.data
node=node.next_node

def__len__(self) ->int:
"""
 >>> for i in range(3):
 ... len(LinkedList(range(i))) == i
 True
 True
 True
 >>> len(LinkedList("abcdefgh"))
 8
 """
returnsum(1for_inself)

def__str__(self) ->str:
"""
 >>> str(LinkedList([]))
 ''
 >>> str(LinkedList(range(5)))
 '0 -> 1 -> 2 -> 3 -> 4'
 """
return" -> ".join([str(node) fornodeinself])

defappend(self, data: int) ->None:
"""
 >>> ll = LinkedList([1, 2])
 >>> tuple(ll)
 (1, 2)
 >>> ll.append(3)
 >>> tuple(ll)
 (1, 2, 3)
 >>> ll.append(4)
 >>> tuple(ll)
 (1, 2, 3, 4)
 >>> len(ll)
 4
 """
ifnotself.head:
self.head=Node(data)
return
node=self.head
whilenode.next_node:
node=node.next_node
node.next_node=Node(data)

defreverse_k_nodes(self, group_size: int) ->None:
"""
 reverse nodes within groups of size k
 >>> ll = LinkedList([1, 2, 3, 4, 5])
 >>> ll.reverse_k_nodes(2)
 >>> tuple(ll)
 (2, 1, 4, 3, 5)
 >>> str(ll)
 '2 -> 1 -> 4 -> 3 -> 5'
 """
ifself.headisNoneorself.head.next_nodeisNone:
return

length=len(self)
dummy_head=Node(0)
dummy_head.next_node=self.head
previous_node=dummy_head

whilelength>=group_size:
current_node=previous_node.next_node
assertcurrent_node
next_node=current_node.next_node
for_inrange(1, group_size):
assertnext_node, current_node
current_node.next_node=next_node.next_node
assertprevious_node
next_node.next_node=previous_node.next_node
previous_node.next_node=next_node
next_node=current_node.next_node
previous_node=current_node
length-=group_size
self.head=dummy_head.next_node


if__name__=="__main__":
importdoctest

doctest.testmod()
ll=LinkedList([1, 2, 3, 4, 5])
print(f"Original Linked List: {ll}")
k=2
ll.reverse_k_nodes(k)
print(f"After reversing groups of size {k}: {ll}")