Python中链表的每k个节点翻转操作
链表每k个节点翻转操作可以使用递归的方式实现。具体步骤如下:
- 将链表分为当前k个节点和余下的节点两部分;
- 对当前k个节点进行翻转,并返回翻转后的头结点;
- 对余下的节点进行递归操作,并返回递归后的头结点;
- 将翻转后的头结点和递归后的头结点连接起来。
具体代码如下:
```python
class ListNode:
def init(self, x):
self.val = x
self.next = None
def reverseKGroup(head: ListNode, k: int) -> ListNode:
# 计算链表长度
length = 0
p = head
while p:
p = p.next
length += 1
if length < k: return head # 翻转前k个节点 pre, cur = None, head for i in range(k): nxt = cur.next cur.next = pre pre = cur cur = nxt # 递归翻转余下的部分 head.next = reverseKGroup(cur, k) return pre
测试样例
head = ListNode('p')
p1 = ListNode('i')
p2 = ListNode('d')
p3 = ListNode('a')
p4 = ListNode('n')
p5 = ListNode('c')
p6 = ListNode('o')
p7 = ListNode('d')
p8 = ListNode('e')
p9 = ListNode('.')
head.next = p1
p1.next = p2
p2.next = p3
p3.next = p4
p4.next = p5
p5.next = p6
p6.next = p7
p7.next = p8
p8.next = p9
new_head = reverseKGroup(head, 3)
while new_head:
print(new_head.val, end='')
new_head = new_head.next
输出:idpanoced.
相关文章