链表22-30

22. 相交链表给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回null。方法一对齐后遍历class Solution(object): def getIntersectionNode(self, headA, headB): num1,num20,0 cur_AheadA cur_BheadB while cur_A: num11 cur_Acur_A.next while cur_B: num21 cur_Bcur_B.next numnum1-num2 cur_AheadA cur_BheadB if num0: while num: cur_Acur_A.next num-1 else: while -num: num1 cur_Bcur_B.next while cur_A!cur_B: cur_Acur_A.next cur_Bcur_B.next return cur_A方法二哈希表class Solution(object): def getIntersectionNode(self, headA, headB): Sset() nodeheadA while node: S.add(node) nodenode.next node headB while node: if node in S: return node nodenode.next return node23.反转链表class Solution(object): def reverseList(self,head): vheadListNode() curhead while cur: headhead.next cur.nextvhead.next vhead.nextcur curhead return vhead.next24. 回文链表快慢指针class Solution(object): def isPalindrome(self, head): val_headListNode(nexthead) fastval_head slowval_head while fast and fast.next: slowslow.next fastfast.next.next val_head.nextNone curslow.next slow.nextNone while cur: newcur.next cur.nextslow.next slow.nextcur curnew curslow.next while cur and head: if cur.valhead.val: curcur.next headhead.next else: return False return True25. 环形链表快慢指针class Solution(object): def hasCycle(self, head): slowhead fasthead while fast and fast.next: slowslow.next fastfast.next.next if slowfast: return True return False26. 环形链表 II哈希表class Solution(object): def detectCycle(self, head): my_dict{} index0 while head: if head in my_dict: return head my_dict[head]index index1 headhead.next return None27. 合并两个有序链表class Solution(object): def mergeTwoLists(self, list1, list2): val_headListNode() tailval_head while list1 and list2: if list1.vallist2.val: curlist1.next tail.nextlist1 taillist1 list1cur else: curlist2.next tail.nextlist2 taillist2 list2cur if list1: tail.nextlist1 if list2: tail.nextlist2 return val_head.next28. 两数相加class Solution(object): def addTwoNumbers(self, l1, l2): carry 0 dummy ListNode(0) cur dummy p, q l1, l2 while p or q or carry: x p.val if p else 0 y q.val if q else 0 total x y carry carry total // 10 cur.next ListNode(total % 10) cur cur.next if p: p p.next if q: q q.next return dummy.next29. 删除链表的倒数第 N 个结点class Solution(object): def removeNthFromEnd(self, head, n): val_nodeListNode(nexthead) fastval_node slowval_node for _ in range(n): fastfast.next while fast.next: fastfast.next slowslow.next slow.nextslow.next.next return val_node.next30. 两两交换链表中的节点class Solution(object): def swapPairs(self, head): val_headListNode(nexthead) curhead while cur and cur.next: datacur.val data_nextcur.next.val cur.valdata_next cur.next.valdata curcur.next.next return val_head.next