《剑指Offer》——链表（Python3 实现）
目录
链表
1、从尾到头打印链表
问题：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：直接遍历一遍链表保存结果到list中，再返回倒序的list即可。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
arr=[]
while listNode:
arr.append(listNode.val)
listNode=listNode.next
return arr[::-1] 2、链表中倒数第K个结点
问题：输入一个链表，输出该链表中倒数第K个结点。
思路：先计算链表的长度，然后计算找到倒数第k个需要几次循环，并判其中关系。最后，用for循环，不断将指针指向下一个节点，即为所求。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val =x
self.next =None
class Solution:
def FindKthToTail(self,head,k):
len_node=0
temp=head
while temp:
temp=temp.next
len_node+=1
run_times=len_node-k
if run_times<0 or k<0:
return
for i in range(run_times):
head=head.next
return head 3、反转链表
问题：输入一个链表，反转链表后，输出链表的所有元素。
思路：利用三个指针逐个翻转（头插法建立单链表）。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val =x
self.next =None
class Solution:
def ReverseList(self,phead):
if not phead:
return
p=phead
q=phead.next
p.next=None
while q:
r=q.next
q.next=p
p=q
q=r
return p 4、合并两个排序的链表
问题：输入两个单调递增的链表，输出两个链表合成后的链表，需要合成后的链表满足单调不减规则。
思路一：迭代方法求解。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val =x
self.next =None
class Solution:
def Merge(self,pHead1,pHead2):
p1=pHead1
p2=pHead2
if p1 and p2: #首先，判断哪个链表的头结点的值小，将值小的作为合并后链表的头结点
if p1.val<=p2.val:
head=p1
p1=p1.next
else:
head=p2
p2=p2.next
r = head
elif p1:
return p1
else:
return p2
while p1 and p2:
if p1.val<=p2.val:
r.next=p1
p1=p1.next
r=r.next
else:
r.next=p2
p2=p2.next
r=r.next
if p1:
r.next=p1
if p2:
r.next=p2
return head 思路二：递归方法。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val =x
self.next =None
class Solution:
def Merge(self,pHead1,pHead2):
merged=None
if not pHead1: #当pHead1为空时，返回pHead2
return pHead2
if not pHead2: #当pHead2为空时，返回pHead1
return pHead1
#第一个链表中的第一个点小于第二个链表中的第二个点，那么merged第一个点就是pHead1的第一个点
#对于它的next，继续执行递归
if pHead1.val<=pHead2.val:
merged=pHead1
pHead1=pHead1.next
merged.next=self.Merge(pHead1,pHead2)
else:
merged=pHead2
pHead2=pHead2.next
merged.next=self.Merge(pHead1,pHead2)
return merged 5、复杂链表的复制
问题：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
# -*- coding:utf-8 -*-
class RandomListNode:
def __init__(self, x):
self.label =x
self.next =None
self.random=None
class Solution:
def Clone(self,pHead):
if not pHead:
return pHead
#开辟一个新结点
copy=RandomListNode(pHead.label)
copy.next=pHead.next
copy.random=pHead.random
#递归剩余的结点
copy.next=self.Clone(pHead.next)
return copy 6、两个链表的第一个公共结点
问题：输入两个链表，找出它们的第一个公共结点。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self,x):
self.val=x
self.next=None
class Solution:
def FindFirstCommonNode(self,pHead1,pHead2):
if not pHead1 or not pHead2:
return None
length1=0
length2=0
p1=pHead1
p2=pHead2
#分别计算两个链表的长度
while p1:
length1+=1
p1=p1.next
while p2:
length2+=1
p2=p2.next
#根据两个链表的长度，确定长、短链表和它们之间的长度差
if length1>=length2:
step=length1-length2
longList=pHead1
shortList=pHead2
else:
step=length2-length1
longList=pHead2
shortList=pHead1
#让长链表先走step步
for i in range(step):
longList=longList.next
#同时遍历两个链表，让他们不断指向next，并判断何时相等，相等时返回任一一个链表即可
while longList and shortList:
if longList==shortList:
return longList
else:
longList=longList.next
shortList=shortList.next
return None 7、链表中环的入口点
问题：一个链表中包含环，请找出该链表的环的入口点。
思路：第一步，找环中相汇点。分别用p，q指向链表头部，p每次走两步，q每次走一步，直到p==q找到在环中的相汇点。
第二步，找环的入口。接上一步，当p==q时，p所经过的节点数为2x，q所经过的节点数为x，设环中有n个节点，p比q多走一个环，有2x=x+n；n=x；可以看出q实际走了一个环的步数，再让p指向链表头部，q位置不变，p，q每次走一步直到p==q；此时p，q指向环的入口。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self,x):
self.val=x
self.next=None
class Solution:
def EntryNodeOfLoop(self,pHead):
if pHead==None:
return None
if pHead.next==None or pHead.next.next==None:
return None
#使用快慢指针，p每次走两步，q每次走一步
p=pHead.next.next
q=pHead.next
#第一次循环，直到p和q相遇，p每次走两步，q每次走一步
while p!=q:
p=p.next.next
q=q.next
if p.next==None or p.next.next==None:
return None
#第二次循环，直到p和q相遇，让快指针p回到开始的点，p和q每次都走一步
p=pHead
while p!=q:
p=p.next
q=q.next
return p 8、删除链表中重复的结点
问题：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5处理后为1->2->5。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self,x):
self.val=x
self.next=None
class Solution:
def deleteDuplication(self,pHead):
temp=[]
head=pHead
#先将pHead中所有结点的value全部放到temp列表中去
while head:
temp.append(head.val)
head=head.next
result=ListNode(0) #创建一个新的指针
head=result #让head指向这个指针
for i in temp:
if temp.count(i)==1: #对于temp中的元素，如果出现次数等于1就添加到head的next指针
head.next=ListNode(i)
head=head.next
return result.next
字节跳动公司氛围 560人发布