【算法第三天7.15】两交换链表节点，删除链表的倒数第 N 个结点，链表相交，环形链表 II

**算法第三天7.15**

### 一、两交换链表节点#### 题目描述：

给定两个链表的头结点 `headA` 和 `headB`,以及一个整数 `x`,要求将链表 A 的第 x 个结点与链表 B 的第 x 个结点进行交换。

#### 解决方案：

class ListNode:
 def __init__(self, val=0, next=None):
 self.val = val self.next = nextdef swapNodes(headA, headB, x):
 # 获取链表 A 和 B 的长度 lenA, lenB =0,0 tempA, tempB = headA, headB while tempA:
 lenA +=1 tempA = tempA.next while tempB:
 lenB +=1 tempB = tempB.next # 确定交换结点的位置 if x > min(lenA, lenB):
 return headA, headB # 交换结点 prevA, prevB = None, None for i in range(x -1):
 prevA = tempA tempA = tempA.next prevB = tempB tempB = tempB.next # 交换结点 tempA.val, tempB.val = tempB.val, tempB.val return headA, headB

def removeNthFromEnd(head, n):
 # 获取链表长度 len =0 temp = head while temp:
 len +=1 temp = temp.next # 确定删除结点的位置 if n == len:
 return head.next # 删除结点 prev = None for i in range(len - n):
 prev = temp temp = temp.next # 删除结点 prev.next = temp.next return head

def getIntersectionNode(headA, headB):
 # 获取链表 A 和 B 的长度 lenA, lenB =0,0 tempA, tempB = headA, headB while tempA:
 lenA +=1 tempA = tempA.next while tempB:
 lenB +=1 tempB = tempB.next # 确定交点的位置 if lenA > lenB:
 for i in range(lenA - lenB):
 headA = headA.next else:
 for i in range(lenB - lenA):
 headB = headB.next # 交点 while headA and headB:
 if headA == headB:
 return headA headA = headA.next headB = headB.next return None

def detectCycle(head):
 # 获取快慢指针 slow, fast = head, head while fast and fast.next:
 slow = slow.next fast = fast.next.next if slow == fast:
 break # 如果没有环形链表，则返回 None if not (slow and fast):
 return None # 将快指针重新置于头结点 fast = head # 将慢指针和快指针重复移动，直到相遇 while slow != fast:
 slow = slow.next fast = fast.next return slow