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

使用哑结点，两个指针交换时多声明几个变量，不容易出错

class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:dummy_head = ListNode(0, head)cur = dummy_headwhile cur.next and cur.next.next:first_node = cur.nextseconde_node = cur.next.nextnext = seconde_node.nextcur.next = seconde_nodeseconde_node.next = first_nodefirst_node.next = nextcur = first_nodereturn dummy_head.next

19.删除链表的倒数第N个节点

快慢指针，题目指出删除的元素肯定在链表中，因此没有判断链表为空的情况。因为要删除倒数第n个元素的时候要指向前一个元素，所以fast先走n+1步

class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy_head = ListNode(next=head)fast = dummy_headslow = dummy_headfor _ in range(n+1):fast = fast.nextwhile fast:fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn dummy_head.next

160.链表相交

先遍历链表得到两个链表的长度，长的链表的指针先走几步，使得和短的链表长度相同，然后两个链表同时开始走，比较节点是否是同一个

class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:# 求两个链表的长度lenA = 0lenB = 0curA = headAcurB = headBwhile curA:curA = curA.nextlenA += 1while curB:curB = curB.nextlenB += 1# 长的链表都设置为A，先走掉gap值if lenA < lenB:headA, headB = headB, headAlenA, lenB = lenB, lenAcurA = headAcurB = headBfor _ in range(lenA-lenB):curA = curA.next# 两个链表一起走while curA:if curA == curB:return curAcurA = curA.nextcurB = curB.nextreturn None

142.环形链表II

首先使用快慢指针判断是否有环，快指针走两步，慢指针走一步，如果能够重合说明有环

然后再找出环的位置，将从此时的位置和链表开始的位置同时走，重合的地方即为环入口的地方

class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:slow = headfast = headwhile fast and fast.next:fast = fast.next.nextslow = slow.next# 重合说明有环if fast == slow:slow = headwhile slow != fast:slow = slow.nextfast = fast.nextreturn slowreturn None