难点:这个需要了解链表的结构,每一个链表除了存储自身的元素之外,还会存储下一个结点的地址,所以要想遍历链表需要从头结点开始,还要注意一旦要是修改了当前结点存储的下一节点的地址,如果我们不使用一个变量记录这个地址,那么后面的链表就会丢失了,所以我们时时刻刻都不能忘记,当前结点的下一个结点的地址。
时间复杂度为O(N)
解决方法:插入法
核心思想是遍历链表,每遍历到一个结点就将其插入到头节点之后,作为头结点之后的第一个结点,比如遍历到b,那么此时它需要把b拿出来放到head后面,并且将a的后继结点的改为c,此时链表变为head->b->a->c,这样遍历完一遍之后就可以了,不用第二遍,而且不需要额外的地址。
代码实现:
class ListNode():
def __init__(self): self.data=None self.next=next
def reverse(ListNode):
if ListNode is None and ListNode.next is None:
return
#获取第二个(当前) cur=ListNode.next.next
ListNode.next.next=None
nextNode=None while cur is not None:
nextNode=cur.next
cur.next=ListNode.next
ListNode.next=cur
cur=nextNodeif __name__ =="__main__" :
LNode=ListNode() p=LNode LNode.data=None LNode.next=None
i=1
while i<=10:
L=ListNode() L.data=i L.next=None
p.next=L
p=L i=i+1
cur=LNode.next
while cur is not None:
print(cur.data)
cur=cur.next
reverse(LNode)
print("反转后")
cur=LNode.next
while cur is not None:
print(cur.data)
cur=cur.next
给定一个链表,然后逆序输出,比如有一个链表head->a->b->c,那么此时我们希望输出c,b,a
我们可以使用递归的形式,(a,b,c)先输出(b,c),然后(b,c)先输出c
时间复杂度O(N)
class Node():
def __init__(self):
self.next=None
self.data=Nonedef ReserverPrint(List): if List is None:
return
ReserverPrint(List.next) print(List.data)if __name__=="__main__":
LNode=Node() p=LNode i=1
while i<10:
l=Node() l.data=i l.next=None
p.next=l p=l i+=1
cur=LNode.next while cur is not None:
print(cur.data) cur=cur.next #反转输出
print("反转输出")
ReserverPrint(LNode.next)
现在有一个链表为head->1->2->3->4->5->6->7,排序之后head->1->7->2->6->3->5->4
我们分析一下,可以看到实际上原始序列的前半部分并没有发生改变,而后半部分是逆序,然后将两个一个一个的插入了,所以说这个的核心是先将后半部分逆序,然后两个链表同时遍历,一个一个的最终形成新的排序链表
这个的意思就是说pre用于指向链表1的第一个结点,cur永远指向链表2的第二个结点,最后返回第一个结点就可以了
class Node():
def __init__(self): self.data=None self.next=None
def firstmiddle(list): if list is None or list.next is None:
return list
first=list two=list while two is not None and two.next is not None:
pre_first=first first=first.next
two=two.next.next
pre_first.next=None
return first
def reverse(list):
if list is None or list.next is None:
return list
cur=list.next
pre=list n_next=cur.next
pre.next=None#这个意思是形成两部分,第一部分有第一个结点->None,第二部分以第二个结点cur直到最后
while cur is not None:
a=cur.next
cur.next=pre
pre=cur cur=a return pre
def Recorder(list): cur1=list.next
mid=firstmiddle(list.next)
cur2=reverse(mid)
while cur1.next is not None:
a=cur1.next#存储cur1,然后再将cur1找回来
cur1.next=cur2
cur1=a a=cur2.next
cur2.next=cur1
cur2=a cur1.next=cur2
if __name__=="__main__":
listNode=Node() p=listNode i=1
while i<=10:
l=Node() l.data=i l.next=None
p.next=l
p=l i+=1
Recorder(listNode) cur=listNode.next
while cur is not None:
print(cur.data)
cur=cur.next
从头开始遍历链表,设置两个指针,其中一个指针每次走两步,另外一个指针每次走一步,那么当走两步的这个只能走到头的时候,那么此时走第一步的这个指针就是指向的中间的元素
设置一个指针one,然后设置一个指针two,two每次走两步,然后one每次走一步,当two走到头之后,one就走到中间了。
如果链表结点数为奇数,那么此时的one就是中间结点,如果链表结点数为偶数,那么此时的one和接下来的一个结点就是中间结点
class Node():
def __init__(self):
self.next=None
self.data=Nonedef FindMiddleNode(ListNode): if ListNode is None or ListNode.next is None:
return ListNode
one=ListNode two=ListNode while two is not None and two.next is not None:
one=one.next two=two.next.next return one
if __name__=="__main__":
ListNode=Node() p=ListNode i=0
while i<10:
l=Node() l.next=None
l.data=i p.next=l p=l i+=1
cur=ListNode.next #原始的列表顺序输出
while cur is not None:
print(cur.data)
cur=cur.next
mid=FindMiddleNode(ListNode.next)
print(mid.data)#输出中间的元素
这个步骤是这样的,主要是将l1链表为主链,思想如下图所示:
class Node():
def __init__(self): self.data=None self.next=None
if __name__=="__main__":
one_listNode=Node() one_p=one_listNode two_listNode = Node() two_p = two_listNode i=1
while i<=10:
l=Node() l.data=i l.next=None
one_p.next=l
one_p=l i+=1
j=11
while j<=20:
l=Node() l.data=j l.next=None
two_p.next=l
two_p=l j+=1
one=one_listNode.next
two=two_listNode.next
a=None while one.next is not None:
a=one.next
one.next=two
one=a a=two.next
two.next=one
two=a one.next=two
n=one_listNode.next
while n is not None:
print(n.data)
n=n.next
我们可以设置两个指针,其中一个指针领先第二个指针k个元素,当第一个指针到链表结尾了,那么第一个指针就是链表的倒数第k个结点。这个只需要遍历一次链表,所以时间复杂度为O(N)
需要注意的是,我们需要时时刻刻地判断这个链表是否长度能够到k,如果本身就没有k个元素,那么倒数第k个元素也是没有意义的
class Node():
def __init__(self): self.next=None self.data=None
def FindlastK(list,k): if list is None or list.next is None:
return
i=0
klist=list first=list #klist比first领先3个元素
while i<k and klist is not None:
klist=klist.next i+=1
if i<k:#如果领先不到3个元素,那么就会出现问题
return
while klist is not None:
klist=klist.next first=first.next return first
if __name__=="__main__":
list=Node() p=list i=1
k=3
n=None while i<=7:
n=Node() n.data=i
n.next=None p.next=n p=n i+=1
first=FindlastK(list,k) print(first.data)
这个意思是这样的,现在有一个单链表头结点->1->2->3->4->5->6->7,此时我们设置k=3,那么我们希望链表可以变为:头结点->5->6->7->1->2->3->4。
这个我们可以先找到倒数第k+1个结点slow,以及原始链表的尾结点fast,然后分割为两个链表,然后进行组合就完成了单链表向右旋转k个位置
class Node():
def __init__(self): self.next=None
self.data=Nonedef RotateK(list,K): if list is None or list.next is None:
return
slow=list.next
fast=list.next
i=0
tmpend=None tmpstart=None while i<=K and fast is not None:
fast=fast.next
i+=1
if i<K:#根本没有k个原元素
return
while fast is not None:
tmpend=fast fast=fast.next
slow=slow.next
tmpstart=slow.next
slow.next=None#断成两条链,第一条链头的list,尾是slow,第二条链头是tmpstart,尾是tmpend
#print(slow.data)
#print(tmpend.data)
#print(tmpstart.data)
tmpend.next=list.next
list.next=tmpstart
if __name__=="__main__":
list=Node() p=list i=1
K=3
while i<=7:
n=Node() n.data=i n.next=None
p.next=n
p=n i+=1
RotateK(list,K) a=list.next
while a is not None:
print(a.data)
a=a.next