python 체인 테이블 제목 및 코드 leetcode 및 검지offer
class Solution:
def printListFromTailToHead(self, listNode):
res=[]
while listNode:
res.insert(0,listNode.val)
listNode=listNode.next
return res
준비 작업: 체인 시계를 출력하는데 코드를 어떻게 코드합니까?출력 체인 테이블 1->2->3
class ListNode:
def __init__(self,x):
self.val=x
self.next=None
def PrintChain(node):
while node:
print node.val
node=node.next
l1=ListNode(1)
l2=ListNode(2)
l3=ListNode(3)
l1.next=l2
l2.next=l3
PrintChain(l1)
2. 체인 테이블을 입력하여 이 체인 테이블의 밑에서 k번째 결점을 출력한다.
class Solution:
def FindKthToTail(self,head,k):
firstPoint=head
secondPoint=head
for i in range(k):
if firstPoint==None:
return None
firstPoint=firstPoint.next
while firstPoint!=None:
firstPoint=firstPoint.next
secondPoint=secondPoint.next
return secondPoint
3. 두 개의 단조로운 체인 테이블을 입력하고 두 개의 체인 테이블을 합성한 체인 테이블을 출력한다. 물론 우리는 합성된 체인 테이블이 단조로운 규칙을 만족시켜야 한다.
class Solution:
def Merge(self, pHead1, pHead2):
if pHead1==None:
return pHead2
elif pHead2==None:
return pHead1
if pHead1.val2. 반전 체인 테이블(또는 반전 중 일부)과 그 응용 반전 체인 테이블;leetcode206. Reverse Linked List
class Solution:
def ReverseList(self, pHead):
pTmp = pHead
newHead = None
while pTmp:
pTmp1 = pTmp.next
pTmp.next = newHead
newHead = pTmp
pTmp = pTmp1
return newHead
생각이 같다
class Solution:
# ListNode
def ReverseList(self, pHead):
if pHead == None:
return None
pTmp = pHead
pTmp1 = pHead.next
newHead = None
while pTmp:
pTmp.next = newHead
newHead = pTmp
pTmp = pTmp1
if pTmp1:
pTmp1 = pTmp1.next
return newHead
leetcode92. Reverse Linked List II 체인 테이블의 일부를 대칭 이동합니다.
class Solution:
def reverseBetween(self, head, m, n):
dummy = ListNode(0) # ：
dummy.next = head
p1 = dummy
for i in range(m-1):
p1 = p1.next
p2 = p1.next
newhead = None
for i in range(n-m+1): # m n
p3 = p2.next
p2.next = newhead
newhead = p2
p2 = p3
p1.next.next = p2
p1.next = newhead
return newhead if p1 == dummy else head
letcode25. Reverse Nodes in k-Group
class Solution:
def reverseKGroup(self, head, k):
i = 0
p = head
p1 = head
while p and ileetcode234. Palindrome Linked List 1->2->2->1 True
# ， O(1)， ，
# ； O(1)： ，
class Solution:
def isPalindrome(self, head):
fastp = slowp = head #
while fastp and fastp.next and slowp:
fastp = fastp.next.next
slowp = slowp.next
newhead = None
while slowp: # ， newhead
p1 = slowp.next
slowp.next = newhead
newhead = slowp
slowp = p1
while newhead and head.val == newhead.val: #
head = head.next
newhead = newhead.next
if newhead == None:
return True
else:
return False
3. 체인표에 링leetcode141이 있는지 판단한다.Linked List Cycle에서 루프 여부를 판단합니다.
class Solution(object):
def hasCycle(self, head):
fastp = slowp = head
while fastp and fastp.next:
fastp = fastp.next.next
slowp = slowp.next
if fastp == slowp:
return True
return False
leetcode142. Linked List Cycle II, 검지는offer 체인 테이블의 링의 입구 노드를 가리킨다. 체인 테이블에 링이 포함되어 있으면, 이 체인 테이블의 링의 입구 결점을 찾아내십시오. 그렇지 않으면 null을 출력합니다.
# a， b， n
# 2*(a+b)=a+b+k*n， a+b=k*n。 ，
# ， ， ， a+b
# n
class Solution(object):
def detectCycle(self, head):
fastp = slowp = head
while fastp and fastp.next:
fastp = fastp.next.next
slowp = slowp.next
if fastp == slowp:
slowp = head
break
if fastp == None or fastp.next == None:
return None
else:
while slowp != fastp:
fastp = fastp.next
slowp = slowp.next
return slowp
class Solution:
def EntryNodeOfLoop(self, pHead):
fastp = slowp = pHead
while fastp and fastp.next:
fastp = fastp.next.next
slowp = slowp.next
if fastp == slowp:
slowp = pHead
break
if fastp == None or fastp.next == None:
return None
else:
while slowp != fastp:
fastp = fastp.next
slowp = slowp.next
return slowp
4. 단방향 체인 시계는 교차점을 찾는다.Intersection of Two Linked Lists는 두 개의 체인 테이블을 입력하여 첫 번째 공통 결점을 찾습니다.법1:
# next， ， next,
class Solution(object):
def getIntersectionNode(self, headA, headB):
lenA = lenB = 0 # A lenA B lenB
pA = headA
pB = headB
while pA:
pA = pA.next
lenA += 1
while pB:
pB = pB.next
lenB += 1
pA = headA
pB = headB
while lenA > lenB: # next
pA = pA.next
lenA -= 1
while lenB > lenA:
pB = pB.next
lenB -= 1
while pA != pB:
pA = pA.next
pB = pB.next
return pA
다음은 검지offer 상응하는 문제 코드입니다.
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
pTmp1=pHead1
pTmp2 = pHead2
while pTmp1 and pTmp2:
pTmp1=pTmp1.next
pTmp2=pTmp2.next
if pTmp1:
k = 0
while pTmp1:
pTmp1 = pTmp1.next
k += 1
pTmp1=pHead1
pTmp2=pHead2
for i in range(k):
pTmp1=pTmp1.next
else:
k=0
while pTmp2:
pTmp2 = pTmp2.next
k += 1
pTmp2=pHead2
pTmp1=pHead1
for i in range(k):
pTmp2=pTmp2.next
while pTmp1 != pTmp2:
pTmp1=pTmp1.next
pTmp2=pTmp2.next
return pTmp1
법2: 함수를 호출하여 두 가지 상황을 호출한다
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
pTmp1 = pHead1
pTmp2 = pHead2
while pTmp1 and pTmp2:
pTmp1 = pTmp1.next
pTmp2 = pTmp2.next
def findequal(longchain,shortchain, longhead, shorthead):
k=0
while longchain:
longchain=longchain.next
k += 1
longchain = longhead
shortchain = shorthead
for i in range(k):
longchain=longchain.next
while longchain != shortchain:
longchain=longchain.next
shortchain=shortchain.next
return longchain
if pTmp1:
return findequal(pTmp1,pTmp2,pHead1,pHead2)
else:
return findequal(pTmp2,pTmp1,pHead2,pHead1)
5. 복수 random 지침leetcode138.Copy List with Random Pointer
class Solution(object):
def copyRandomList(self, head):
if head == None:
return None
p = head
while p: #
node = Node(p.val, p.next, p.random)
node.next = p.next
p.next = node
p = node.next
p = head
while p: # random
if p.random:
p.next.random = p.random.next
p = p.next.next
p = head
newhead = p.next
p1 = newhead
while p and p1.next: #
p.next = p1.next
p = p.next
p1.next = p.next
p1 = p1.next
p.next = None
p1.next = None
return newhead
대응하는 검지offer 제목: 하나의 복잡한 체인 테이블(각 노드에 노드 값이 있고 두 개의 바늘이 있는데 하나는 다음 노드를 가리키고 다른 특수한 바늘은 임의의 노드를 가리킨다)을 입력하면 복사 후 복잡한 체인 테이블의head로 되돌아온다.(출력 결과에서 매개 변수의 노드 인용을 되돌려주지 마십시오. 그렇지 않으면 판정 프로그램이 바로 비어 있습니다.) 방법 1:
import copy
class Solution:
# RandomListNode
def Clone(self, pHead):
# write code here
ret=copy.deepcopy(pHead)
return ret
방법2:
class Solution:
# RandomListNode
def Clone(self, pHead):
# write code here
if pHead == None:
return None
pTmp = pHead
while pTmp:
node = RandomListNode(pTmp.label)
node.next = pTmp.next
pTmp.next = node
pTmp = node.next
pTmp = pHead
while pTmp:
if pTmp.random:
pTmp.next.random = pTmp.random.next
pTmp = pTmp.next.next
pTmp = pHead
pTmp1 = pHead.next
newhead = pHead.next
while pTmp:
pTmp.next = pTmp.next.next
pTmp=pTmp.next
if pTmp1.next:
pTmp1.next = pTmp1.next.next
pTmp1=pTmp1.next
return newhead
주:pycharm 디버깅을 하려면
if __name__ == "__main__":
n1=RandomListNode(1)
n2 = RandomListNode(2)
n3 = RandomListNode(3)
n4 = RandomListNode(4)
n1.next = n2
n2.next = n3
n3.next = n4
s=Solution()
newhead = s.Clone(n1)
tmp = newhead
while tmp:
print tmp.label
tmp = tmp.next
** 6, 체인 테이블 partition ** leetcode 86.Partition List: 체인 테이블에 정수를 저장하고 x를 주고 x보다 작은 노드를 >=x 앞에 두기
# ： ， x leftp ， rightp ，
class Solution:
def partition(self, head, x):
dummyleft = ListNode(0)
dummyright = ListNode(0)
leftp = dummyleft
rightp = dummyright
p = head
while p:
if p.val < x:
leftp.next = p
leftp = leftp.next
else:
rightp.next = p
rightp = rightp.next
p = p.next
rightp.next = None
leftp.next = dummyright.next
return dummyleft.next
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
