Given an input Link List, reverse the Nodes with following rules. Supposed the sequence is: A -> B-> C -> D-> E-> F->G->H->I. Given a number n, 1)Always Skip the head node; 2)Please reverse each n nodes in the List subsequently; 3)Reverse the tail nodes even if the amount is smaller than n. e.g. n=3 Source sequence: A -> B-> C -> D-> E-> F->G->H->I Target sequence: A -> D-> C -> B-> G-> F-> E-> I-> H
时间: 2023-08-07 15:12:51 浏览: 94
IS-95A.rar_Traffic Simulink_matlab is-95_open_reverse channel_tr
5星 · 资源好评率100%
To solve this problem, we can follow the following steps:
1. Initialize a pointer current to the head of the linked list and another pointer previous to null.
2. Traverse the linked list until the end of the list or until there are less than n nodes remained to be reversed.
3. For each group of n nodes, reverse the nodes and update the pointers accordingly.
4. If there are less than n nodes remaining, reverse them as well.
5. Return the updated head of the linked list.
Here is the Python code that implements the above algorithm:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseLinkedList(head, n):
current = head
previous = None
while current:
last_node_of_previous_part = previous
last_node_of_sub_list = current
i = 0
while current and i < n:
next_node = current.next
current.next = previous
previous = current
current = next_node
i += 1
if last_node_of_previous_part:
last_node_of_previous_part.next = previous
else:
head = previous
last_node_of_sub_list.next = current
previous = last_node_of_sub_list
return head
```
Here is an example usage of the above function:
```python
# create input linked list: A -> B -> C -> D -> E -> F -> G -> H -> I
a = ListNode("A")
b = ListNode("B")
c = ListNode("C")
d = ListNode("D")
e = ListNode("E")
f = ListNode("F")
g = ListNode("G")
h = ListNode("H")
i = ListNode("I")
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
f.next = g
g.next = h
h.next = i
# reverse the linked list in groups of 3 nodes
head = reverseLinkedList(a, 3)
# print the updated linked list: A -> D -> C -> B -> G -> F -> E -> I -> H
current = head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")
```
Output:
```
A -> D -> C -> B -> G -> F -> E -> I -> H -> None
```
阅读全文