document.write('
主要思路为:首先把前K个结点看成一个子链表,采用前面介绍的方法进行翻转,把翻转后的子链表链
接到头结点后面,然后把接下来的K个结点看成另外一个单独的链表进行翻转,把翻转后的子链表链接
到上一个已经完成翻转子链表的后面。具体实现方法如下图所示。
在上图中,以K=3为例介绍具体实现的方法:
(1)首先设置pre指向头结点,然后让begin指向链表第一个结点,找到从begin开始第K=3个结点
end。
(2)为了采用本章第一节中链表翻转的算法,需要使end.next=None在此之前需要记录下end指向的
结点,用pNext来记录。
(3)使end.next=None,从而使得从begin到end为一个单独的子链表。
(4)对以begin为第一个结点,end为尾结点所对应的K=3个结点进行翻转。
(5)由于翻转后子链表的第一个结点从begin变为end,因此,执行pre.next=end,把翻转后的子链
表链接起来。
(6)把链表中剩余的还未完成翻转的子链表链接到已完成翻转的子链表后面(主要是针对剩余的结点的
个数小于K的情况)。
(7)让pre指针指向已完成翻转的链表的最后一个结点。
(8)让begin指针指向下一个需要被翻转的子链表的第一个结点(通过begin=pNext来实现)。
接下来可以反复使用(1)~(8)8个步骤对链表进行翻转。实现代码如下:
class LNode:
def __new__(self,x):
self.data=x
self.next=None
# 对不带头结点的单链表翻转
def Reverse(head):
if head==None or head.next==None:
return head
pre=head #前驱结点
cur=head.next #当前结点
next=cur.next# 后继结点
pre.next=None
#使当前遍历到的结点cur指向其前驱结点
while cur!=None:
next=cur.next
cur.next=pre
pre=cur
cur=cur.next
cur=next
return pre
# 对链表K翻转
def ReverseK(head,k):
if head==None or head.next==None or k<2:
return
i=1
pre=head
begin=head.next
end=None
pNext=None
while begin!=None:
end=begin
# 对应图中第(1)步,找到从begin开始第K个结点
while i<k:
if end.next!=None:
end=end.next
else: #剩余结点的个数小于K
return
i+=1
pNext=end.next #(2)
end.next=None #(3)
pre.next=Reverse(begin) #(4) (5)
begin.next=pNext #(6)
pre=begin #(7)
begin=pNext #(8)
i=1
if __name__=="__main__":
i=1
head=LNode()
head.next=None
tmp=None
cur=head
while i<8:
tmp=LNode()
tmp.data=i
tmp.next=None
cur.next=tmp
cur=tmp
i+=1
print "顺序输出: ",
cur=head.next
while cur!=None:
print cur.data,
cur=cur.next
ReverseK(head,3)
print "\\n逆序输出: ",
cur=head.next
while cur!=None:
print cur.data,
cur=cur.next
cur=head.next
while cur!=None:
tmp=cur
cur=cur.next
程序的运行结果为:
顺序输出:1 2 3 4 5 6 7
逆序输出:3 2 1 6 5 4 7
运行结果分析:
由于K=3,因此,链表可以分成三组(1 2 3)、(4 5 6)、(7)。对(1 2 3)翻转后变为(3 2 1),对(4 5 6)
翻转后变为(6 5 4),由于(7)这个子链表只有1个结点(小于3个),因此,不进行翻转,所以,翻转后的链
表就变为:3->2->1->6->5->4->7。
算法性能分析:
这种方法只需要对链表进行一次遍历,因此,时间复杂度为O(n)。另外由于只需要几个指针变量来保
存结点的地址信息,因此,空间复杂度为O(1)。
');