1. reverse LinkedList
1 class ListNode: 2 def __init__(self,x): 3 self.val=x 4 self.next=None 5 6 class Solution: 7 def reverse(self,head): 8 if(head==None or head.next==None): 9 return head 10 11 cur=head 12 pre=None 13 while(cur): 14 next=cur.next 15 cur.next=pre 16 pre=cur 17 cur=next 18 return pre 19 20 def print_list(self,head): 21 while(head): 22 print(head.val) 23 head=head.next 24 25 26 n1=ListNode(1) 27 n2=ListNode(2) 28 n3=ListNode(3) 29 n4=ListNode(4) 30 n5=ListNode(5) 31 n1.next=n2 32 n2.next=n3 33 n3.next=n4 34 n4.next=n5 35 s=Solution() 36 res=s.reverse(n1) 37 s.print_list(res)
2. reverse list from m to n
1 #coding:utf-8 2 class ListNode: 3 def __init__(self,x): 4 self.val=x 5 self.next=None 6 7 class Solution: 8 def reverse_m_n(self,head,m,n): 9 pre=None 10 cur=head 11 for i in range(m-1): 12 pre=cur 13 cur=cur.next 14 15 # 需要将n-m+1个节点逆置 16 tail=pre 17 for i in range(n-m+1): 18 next=cur.next 19 cur.next=tail 20 tail=cur 21 cur=next 22 23 24 if(pre): # m≠1 25 pre.next.next=cur 26 pre.next=tail 27 return head 28 else: # m=1 29 head.next=cur 30 return tail 31 32 33 def print_list(self,head): 34 while(head): 35 print(head.val) 36 head=head.next 37 38 39 n1=ListNode(1) 40 n2=ListNode(2) 41 n3=ListNode(3) 42 n4=ListNode(4) 43 n5=ListNode(5) 44 n1.next=n2 45 n2.next=n3 46 n3.next=n4 47 n4.next=n5 48 s=Solution() 49 # s.print_list(n1) 50 res=s.reverse_m_n(n1,2,4) 51 s.print_list(res)
3. intersection of two list
1 class ListNode: 2 def __init__(self,x): 3 self.val=x 4 self.next=None 5 6 7 class Solution: 8 def getIntersection(self,l1,l2): 9 if(l1==None or l2==None): 10 return None 11 12 p1,p2=l1,l2 13 while(p1 and p2): 14 p1=p1.next if(p1) else l2 15 p2=p2.next if(p2) else l1 16 17 if(p1==p2): 18 return p1 19 return None 20 21 n1=ListNode(1) 22 n2=ListNode(2) 23 n3=ListNode(3) 24 n4=ListNode(4) 25 n5=ListNode(5) 26 n1.next=n3 27 n3.next=n4 28 n4.next=n5 29 s=Solution() 30 print(s.getIntersection(n1,n2).val)
4. cycle list
1 class ListNode: 2 def __init__(self,x): 3 self.val=x 4 5 class Solution: 6 def detectCycle(self,head): 7 if(head==None or head.next==None): 8 return head 9 10 slow,fast=head,head 11 iscycle=False 12 while(fast and fast.next): 13 slow=slow.next 14 fast=fast.next.next 15 if(slow==fast): 16 iscycle=True 17 break 18 19 if(not iscycle): 20 return None 21 22 fast=head 23 while(fast!=slow): 24 slow=slow.next 25 fast=fast.next 26 27 return fast 28 29 n1=ListNode(1) 30 n2=ListNode(2) 31 n3=ListNode(3) 32 n4=ListNode(4) 33 n5=ListNode(5) 34 n6=ListNode(6) 35 n7=ListNode(7) 36 37 n1.next=n2 38 n2.next=n3 39 n3.next=n4 40 n4.next=n5 41 n5.next=n6 42 n6.next=n7 43 n7.next=n3 44 s=Solution() 45 print(s.detectCycle(n1).val) 46
5. partition list
1 class ListNode: 2 def __init__(self,x): 3 self.val=x 4 self.next=None 5 6 class Solution: 7 def partition(self,head,x): 8 head1=ListNode(-1); 9 head2=ListNode(-1); 10 l1,l2=head1,head2 11 12 while(head): 13 if head.val<x: 14 l1.next=head 15 head=head.next 16 l1=l1.next 17 else: 18 l2.next=head 19 head=head.next 20 l2=l2.next 21 22 l2.next=None 23 l1.next=head2.next 24 return head1.next 25 26 def print_list(self,head): 27 while(head): 28 print(head.val) 29 head=head.next 30 31 n1=ListNode(1) 32 n2=ListNode(4) 33 n3=ListNode(3) 34 n4=ListNode(2) 35 n5=ListNode(5) 36 n6=ListNode(2) 37 38 n1.next=n2 39 n2.next=n3 40 n3.next=n4 41 n4.next=n5 42 n5.next=n6 43 44 s=Solution() 45 res=s.partition(n1,3) 46 print(s.print_list(res)) 47
6. copy random list
1 class Node: 2 def __init__(self,x,next=None,random=None): 3 self.val=x 4 self.next=next 5 self.random=next 6 7 class Solution(object): 8 def copyList(self, head): 9 if(head==None): 10 return head 11 12 newHead=Node(head.val) 13 hash=dict() 14 hash[head]=newHead 15 16 cur=head.next 17 while(cur): 18 hash[cur]=Node(cur.val) 19 cur=cur.next 20 21 22 cur=head 23 while(cur): 24 if(cur.next): 25 hash[cur].next=hash[cur.next] 26 if(cur.random): 27 hash[cur].random=hash[cur.random] 28 cur=cur.next 29 30 return hash[head] 31 32 def print_list(self,l): 33 while(l): 34 print(l.val) 35 l=l.next 36 37 n1=Node(5) 38 n2=Node(3) 39 n3=Node(6) 40 n1.next=n2 41 n2.next=n3 42 # n1.random=n3 43 # n2.random=n1 44 # n3.random=n3 45 46 s=Solution() 47 res=s.copyList(n1) 48 # print(res.next.val) 49 # print(res.next.next.val) 50 # print(res.next.next.next.val) 51 s.print_list(res) 52 53
7. mergeKSortedLists
1 # Definition for singly-linked list. 2 # class ListNode(object): 3 # def __init__(self, x): 4 # self.val = x 5 # self.next = None 6 7 from Queue import PriorityQueue 8 class Solution(object): 9 def mergeKLists(self, lists): 10 if(len(lists)==0): 11 return None 12 if(len(lists)==1): 13 return lists[0] 14 15 pq=PriorityQueue() 16 for l in lists: 17 if(l): # [[],[]] 18 pq.put((l.val,l)) 19 20 dummy=ListNode(-1) 21 tail=dummy 22 while(pq.qsize()!=0): 23 cur=pq.get()[1] 24 tail.next=cur 25 tail=tail.next 26 27 if(cur.next): 28 pq.put((cur.next.val,cur.next)) 29 30 return dummy.next 31 32