剑指offer刷题日记-链表

Abigail ·

更新时间:2024-09-21

· 534 次阅读

链表03-从尾到头打印链表（python）

#采用insert方法

class Solution:
	def printlist(self,listNode):
		if not listNode:
			return []
		result=[]
		while listNode:
			result.insert(0,listNode.val)
			listNode=listNode.next
		return result

链表014-链表中倒数第k个节点（python）

#采用快慢指针

class Solution:
	def FindkthTotail(self,head,k):
		if not head:
			return None
		fast=head
		slow=head
		for i in range(k):
			if fast!=None:
				fast=fast.next
			else:
				return None
		while fast:
			fast=fast.next
			slow=slow.next
		return slow

链表015-反转链表（python）

class Solution:
	def Reverselist(self,head):
		if not head:
			return None
		last=None
		while head:
			temp=head.next
			head.next=last
			last=head
			head=temp
		return last

链表016-合并两个有序链表（python）
#迭代

class Solution:
	def Merge(self,phead1,phead2):
		if phead1=None:
			return phead2
		if phead2=None:
			return phead1
		pMergehead=None
		if phead1.val<phead2.val:
			pMergehead=phead1
			pMergehead=self.Merge(phead1.next,phead2)
		else:
			pMergehead=phead2
			pMergehead=self.Merge(phead1,phead2.next)
		return pMergehead

链表025-复杂链表的复制（python）
#复制节点，复制random，拆分

class Solution:
	def clone(self,phead):
		if not phead:
			return None
		pNode=phead
		while pNode:
			pclone=RandomListNode(pNode.label)
			pclone.next=pNode.next
			pNode.next=pclone
			pNode=pclone.next
		pNode=phead
		while pNode:
			pclone=pNode.next
			if pNode.random!=None:
				pclone.random=pNode.random.next
			pNode=pclone.next
		pNode=phead
		pcloneHead=pcloneNode=pNode.next
		pNode.next=pcloneHead.next
		while pNode:
			pcloneNode.next=pNode.next
			pcloneNode=pcloneNode.next
			pclone.next=pcloneNode.next
			pNode=pNode.next
		return pcloneHead

链表036-两个链表的第一个公共节点（python）

class Solution:
	def FindFirst(self,phead1,phead2):
		if not phead1 or not phead2:
			return None
		p1,p2=phead1,phead2
		count_1=count_2=0
		while phead1:
			p1=p1.next
			count_1+=1
		while phead2:
			p2=p2.next
			count_2+=1
		if count_1>count_2:
			while(count_1-count_2):
				phead1=phead1.next
				count_1-=1
		else:
			while(count_2-count_1):
				phead2=phead2.next
				count_2-=1
		while phead1 and phead2:
			if phead1.val==phead2.val:
				return phead1
			phead1=phead1.next
			phead2=phead2.next
		return None

链表055-链表中的入口节点（python）
#快慢指针

class Solution:
	def EntryNodeOfLoop(self,phead):
		if not phead or not phead.next:
			return None
		fast=phead.next
		slow=phead
		while fast!=slow and fast.next:
			fast=fast.next.next
			slow=slow.next
		if fast=slow:
			fast=phead
			while fast!=slow:
				fast=fast.next
				slow=slow.next
			return fast
		return None

链表056-删除链表中重复节点（python）

class Solution:
	def deleteDuplication(self,phead):
		head=ListNode(0)
		head.next=phead
		pre=head
		p=phead
		while p and p.next:
			if p.val==p.next.val:
				while p.next and p.next.val=p.val:
					p.next=p.next.next
				pre.next=p.next
				p=pre.next
			else:
				pre=p
				p=p.next
		return head.next