從最基礎(chǔ)的翻轉(zhuǎn)鏈表開始:
def reverse_linklist(l):
prev = None
head = l.head
while head:
tmp = head.next
head.next = prev
prev = head
head = tmp
好距贷，我們開始計(jì)算K個(gè)一組翻轉(zhuǎn)列表:
- k個(gè)一組的數(shù)組翻轉(zhuǎn)
- 組個(gè)組的之間的指針的指向修改
# coding: utf-8
class LinkListNode(object):
def __init__(self, value):
self.value = value
self.next = None
def k_reverse_list(head, k):
# 首先需要構(gòu)造pre指針指向組
pre = LinkListNode(None)
pre.next = head
# 需要一個(gè)固定的指針指向聯(lián)表的頭部, 最后好返回整個(gè)鏈表
hair = pre
while head:
tail = head
for i in range(k):
# k個(gè)分組
tail = tail.next
if not tail:
break
# 設(shè)置lnext保存下一個(gè)k組
lnext = tail.next
# 翻轉(zhuǎn)組內(nèi)的數(shù)據(jù)
rhead, rtail = reverse_group(head, tail)
# 使得pre指針指向翻轉(zhuǎn)后的組, 并且tail指向下一個(gè)組的開始節(jié)點(diǎn)
# pre指針移動(dòng)到tail, head指針移動(dòng)到tail.next
pre.next = rhead
rtail.next = lnext
pre = tail
head = lnext
return hair.next
def reverse_group(head, tail):
# 翻轉(zhuǎn)之后tail.next為pre
# [A --> B --> C] --> [D --> E]
# [C --> B --> A] --> [E --> D]
pre = tail.next
p = head
while pre != p:
t_next = p.next
p.next = pre
pre = p
p = t_next
return tail, head
