24. 两两交换链表中的节点题目链接24. 两两交换链表中的节点 - 力扣LeetCode给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。比如题解首先在链表头部添加一个哨兵节点是其指向节点1我觉得是想构建一个循环体因为除了前两个节点以及最后的节点外中间每两个要交换的节点都是前面有节点连接交换后的这两个节点其次即图中蓝色部分接着黄色箭头进入下一组节点中虚拟头节点 迭代交换# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0,head) cur dummy while cur.next and cur.next.next: #先存储要交换的节点 node1 cur.next node2 cur.next.next #交换节点 tmp node2.next node2.next node1 node1.next tmp cur.next node2 #连接当前节点与交换后的两个节点 cur node1 return dummy.next19.删除链表的倒数第N个节点题目链接19. 删除链表的倒数第 N 个结点 - 力扣LeetCode给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。题解在链表中删除某个节点一般是跳过中间节点前后节点直接连接但是有两种特殊情况如果删除的是头节点此时需要添加一个哨兵节点dummy使dummy.nexthead如果删除的是尾节点此时直接另尾节点的前一节点指向None即可。由于需要删除的是倒数第n个节点此时比较易想的是想遍历一次得到链表总长然后再遍历一次到L-n1进行删除操作但是看到一种很有趣的解法使用双指针策略或者叫快慢指针当right指针走到第n个节点时left指针开始走当right指针走完链表时left指针刚好指向倒数第n1个节点。建议大家画下来可以更好理解# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: left right dummy ListNode(0,head) for _ in range(n): right right.next while right.next: left left.next right right.next left.next left.next.next return dummy.next面试题 02.07. 链表相交题目链接面试题 02.07. 链表相交给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回null。题解在链表相交问题里指针相等 ≠ 节点值val相等而是指两个链表的节点引用指针指向同一个内存地址的同一个节点对象。我们可以把每个链表节点想象成一个「独立的小盒子」每个盒子都有唯一的内存地址就像门牌号节点值val盒子里装的东西比如数字 3、字符串 a指针引用指向这个盒子的门牌号「指针相等」就是两个指针拿着同一个门牌号指向同一个盒子。# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: lenA, lenB 0, 0 curA, curB headA, headB while curA: curA curA.next lenA1 while curB: curB curB.next lenB1 curA, curB headA, headB if lenA lenB: curA, curB headB, headA lenA, lenB lenB, lenA for _ in range(lenB-lenA): curB curB.next while curA: if curA curB: return curA curA curA.next curB curB.next return None142.环形链表II题目链接https://leetcode.cn/problems/linked-list-cycle-ii给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。