链表22-30

22. 相交链表

给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。

方法一：对齐后遍历

class Solution(object): def getIntersectionNode(self, headA, headB): num1,num2=0,0 cur_A=headA cur_B=headB while cur_A: num1+=1 cur_A=cur_A.next while cur_B: num2+=1 cur_B=cur_B.next num=num1-num2 cur_A=headA cur_B=headB if num>0: while num: cur_A=cur_A.next num-=1 else: while -num: num+=1 cur_B=cur_B.next while cur_A!=cur_B: cur_A=cur_A.next cur_B=cur_B.next return cur_A

方法二：哈希表

class Solution(object): def getIntersectionNode(self, headA, headB): S=set() node=headA while node: S.add(node) node=node.next node =headB while node: if node in S: return node node=node.next return node

23.反转链表

class Solution(object): def reverseList(self,head): vhead=ListNode() cur=head while cur: head=head.next cur.next=vhead.next vhead.next=cur cur=head return vhead.next

24. 回文链表

快慢指针

class Solution(object): def isPalindrome(self, head): val_head=ListNode(next=head) fast=val_head slow=val_head while fast and fast.next: slow=slow.next fast=fast.next.next val_head.next=None cur=slow.next slow.next=None while cur: new=cur.next cur.next=slow.next slow.next=cur cur=new cur=slow.next while cur and head: if cur.val==head.val: cur=cur.next head=head.next else: return False return True

25. 环形链表

快慢指针

class Solution(object): def hasCycle(self, head): slow=head fast=head while fast and fast.next: slow=slow.next fast=fast.next.next if slow==fast: return True return False

26. 环形链表 II

哈希表

class Solution(object): def detectCycle(self, head): my_dict={} index=0 while head: if head in my_dict: return head my_dict[head]=index index+=1 head=head.next return None

27. 合并两个有序链表

class Solution(object): def mergeTwoLists(self, list1, list2): val_head=ListNode() tail=val_head while list1 and list2: if list1.val<list2.val: cur=list1.next tail.next=list1 tail=list1 list1=cur else: cur=list2.next tail.next=list2 tail=list2 list2=cur if list1: tail.next=list1 if list2: tail.next=list2 return val_head.next

28. 两数相加

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.next

29. 删除链表的倒数第 N 个结点

class Solution(object): def removeNthFromEnd(self, head, n): val_node=ListNode(next=head) fast=val_node slow=val_node for _ in range(n): fast=fast.next while fast.next: fast=fast.next slow=slow.next slow.next=slow.next.next return val_node.next

30. 两两交换链表中的节点

class Solution(object): def swapPairs(self, head): val_head=ListNode(next=head) cur=head while cur and cur.next: data=cur.val data_next=cur.next.val cur.val=data_next cur.next.val=data cur=cur.next.next return val_head.next