Python中链表的每k个节点翻转操作

2023-04-11 00:00:00 节点 链表 翻转

链表每k个节点翻转操作可以使用递归的方式实现。具体步骤如下:

  1. 将链表分为当前k个节点和余下的节点两部分;
  2. 对当前k个节点进行翻转,并返回翻转后的头结点;
  3. 对余下的节点进行递归操作,并返回递归后的头结点;
  4. 将翻转后的头结点和递归后的头结点连接起来。

具体代码如下:

```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.

相关文章