链表
2019-04-15 本文已影响0人
cookyo
1 合并两个链表
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
p1 = pHead1
p2 = pHead2
p3 = ListNode(0)
p = p3
while p1 and p2:
if p1.val >= p2.val:
p3.next = p2
p2 = p2.next
else:
p3.next = p1
p1 = p1.next
p3 = p3.next
if p1:
p3.next = p1
else:
p3.next = p2
return p.next
2 链表判环 并返回入环节点的值
class ChkLoop:
def chkLoop(self, head, adjust):
# write code here
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast.val
return -1
3 两个无环单链表是否相交
class CheckIntersect:
def chkIntersect(self, headA, headB):
# write code here
lenA = 0
lenB = 0
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:
if lenA > lenB:
pA = pA.next
lenA -= 1
else:
pB = pB.next
lenB -= 1
while pA:
if pA == pB:
return True
pA = pA.next
pB = pB.next
return False
4 合并两个有序链表
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
p1 = pHead1
p2 = pHead2
p3 = ListNode(0)
p = p3
while p1 and p2:
if p1.val >= p2.val:
p3.next = p2
p2 = p2.next
else:
p3.next = p1
p1 = p1.next
p3 = p3.next
if p1:
p3.next = p1
else:
p3.next = p2
return p.next
5 链表排序
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
return self.mergeSort(head)
def mergeSort(self, head):
if head is None or head.next is None:
return head
fast = slow = head
while fast and fast.next:
fast = fast.next.next
breakN = slow
slow = slow.next
breakN.next = None
l1 = self.mergeSort(head)
l2 = self.mergeSort(slow)
return self.merge(l1, l2)
def merge(self, l1, l2):
if l1 is None:
return l2
if l2 is None:
return l1
if l1.val <= l2.val:
l1.next = self.merge(l1.next, l2)
return l1
else:
l2.next = self.merge(l2.next, l1)
return l2
