两两交换链表中的节点题目给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例 1 输入head [1,2,3,4] 输出[2,1,4,3] 示例 2 输入head [] 输出[] 示例 3 输入head [1] 输出[1] 提示 链表中节点的数目在范围 [0, 100] 内 0 Node.val 100思路用虚拟头节点然后三个指针交换顺序判断条件就是当前节点的下一个或者下下个是不是None代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def swapPairs(self, head: ListNode) - ListNode: dummy_head ListNode(nexthead) current dummy_head # 必须有cur的下一个和下下个才能交换否则说明已经交换结束了 while current.next and current.next.next: temp current.next # 防止节点修改 temp1 current.next.next.next current.next current.next.next current.next.next temp temp.next temp1 current current.next.next return dummy_head.next注意点1. 谁会断谁就得用一个临时变量保存2. and运算法注意前面是next后面是next.next因为and是短路运算法如果next.next放前面会出现空指针异常因为如果只有一个后继下一个指针不知道指向的哪里题目链接24. 两两交换链表中的节点 - 力扣LeetCode删除链表的倒数第N个节点题目给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 示例 1 输入head [1,2,3,4,5], n 2 输出[1,2,3,5] 示例 2 输入head [1], n 1 输出[] 示例 3 输入head [1,2], n 1 输出[1] 提示 链表中结点的数目为 sz 1 sz 30 0 Node.val 100 1 n sz思路快慢指针一个在前面找到最后一个None另外一个用来删除节点然后注意因为删除一个节点需要使用前一个节点才能删掉这个节点所以这里需要让快指针再多走一步代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) - ListNode: # 创建一个虚拟节点并将其下一个指针设置为链表的头部 dummy_head ListNode(0, head) # 创建两个指针慢指针和快指针并将它们初始化为虚拟节点 slow fast dummy_head # 快指针比慢指针快 n1 步 for i in range(n1): fast fast.next # 移动两个指针直到快速指针到达链表的末尾 while fast: slow slow.next fast fast.next # 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点 slow.next slow.next.next return dummy_head.next题目链接19. 删除链表的倒数第 N 个结点 - 力扣LeetCode链表相交题目思路把二者相差的长度剪掉这样后面就是同样的长度然后比较一下地址如果相同就说明一样如果到最后地址都不相同就说明不对需要注意的点1. 判断想不想等用的是is而不是因为我们判断的是地址是否相同而不是数值代码class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode): lenA 0 lenB 0 curA headA curB headB # 计算 A 的长度 while curA: lenA 1 curA curA.next # 计算 B 的长度 while curB: lenB 1 curB curB.next # 指针重新回到头节点 curA headA curB headB # 较长链表先走长度差 if lenA lenB: for _ in range(lenA - lenB): curA curA.next else: for _ in range(lenB - lenA): curB curB.next # 一一比较节点 while curA: if curA is curB: return curA curA curA.next curB curB.next return None题目链接面试题 02.07. 链表相交 - 力扣LeetCode环形链表II题目思路1. 判断是否有环路首先快慢指针一个每次走一步一个每次走两步然后判断是否有一个时刻想等如果想等说明是环路但是注意判断条件当前fast和fast.next因为fast指针一次走两个需要判断下一个是不是空2. 判断环路在哪里成环这里就需要一个数学计算slow x yfast x y n(y z) (n1)速度比 1:22(xy) x y n(y z)求x x (n-1)(yz) z当n 1x z当n1 x n-1圈 z说明x和z一样长说明指针从相遇的地方走到环的开头 和 从head走到环的开头一样长就能 设处一个等式最后得到结果代码#版本一快慢指针法 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def detectCycle(self, head: ListNode) - ListNode: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # If there is a cycle, the slow and fast pointers will eventually meet if slow fast: # Move one of the pointers back to the start of the list slow head while slow ! fast: slow slow.next fast fast.next return slow # If there is no cycle, return None return None题目链接142. 环形链表 II - 力扣LeetCode总结链表就是虚拟头节点很重要其他的就是运用链表的性质来做
Day4 链表 part2
两两交换链表中的节点题目给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例 1 输入head [1,2,3,4] 输出[2,1,4,3] 示例 2 输入head [] 输出[] 示例 3 输入head [1] 输出[1] 提示 链表中节点的数目在范围 [0, 100] 内 0 Node.val 100思路用虚拟头节点然后三个指针交换顺序判断条件就是当前节点的下一个或者下下个是不是None代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def swapPairs(self, head: ListNode) - ListNode: dummy_head ListNode(nexthead) current dummy_head # 必须有cur的下一个和下下个才能交换否则说明已经交换结束了 while current.next and current.next.next: temp current.next # 防止节点修改 temp1 current.next.next.next current.next current.next.next current.next.next temp temp.next temp1 current current.next.next return dummy_head.next注意点1. 谁会断谁就得用一个临时变量保存2. and运算法注意前面是next后面是next.next因为and是短路运算法如果next.next放前面会出现空指针异常因为如果只有一个后继下一个指针不知道指向的哪里题目链接24. 两两交换链表中的节点 - 力扣LeetCode删除链表的倒数第N个节点题目给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 示例 1 输入head [1,2,3,4,5], n 2 输出[1,2,3,5] 示例 2 输入head [1], n 1 输出[] 示例 3 输入head [1,2], n 1 输出[1] 提示 链表中结点的数目为 sz 1 sz 30 0 Node.val 100 1 n sz思路快慢指针一个在前面找到最后一个None另外一个用来删除节点然后注意因为删除一个节点需要使用前一个节点才能删掉这个节点所以这里需要让快指针再多走一步代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) - ListNode: # 创建一个虚拟节点并将其下一个指针设置为链表的头部 dummy_head ListNode(0, head) # 创建两个指针慢指针和快指针并将它们初始化为虚拟节点 slow fast dummy_head # 快指针比慢指针快 n1 步 for i in range(n1): fast fast.next # 移动两个指针直到快速指针到达链表的末尾 while fast: slow slow.next fast fast.next # 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点 slow.next slow.next.next return dummy_head.next题目链接19. 删除链表的倒数第 N 个结点 - 力扣LeetCode链表相交题目思路把二者相差的长度剪掉这样后面就是同样的长度然后比较一下地址如果相同就说明一样如果到最后地址都不相同就说明不对需要注意的点1. 判断想不想等用的是is而不是因为我们判断的是地址是否相同而不是数值代码class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode): lenA 0 lenB 0 curA headA curB headB # 计算 A 的长度 while curA: lenA 1 curA curA.next # 计算 B 的长度 while curB: lenB 1 curB curB.next # 指针重新回到头节点 curA headA curB headB # 较长链表先走长度差 if lenA lenB: for _ in range(lenA - lenB): curA curA.next else: for _ in range(lenB - lenA): curB curB.next # 一一比较节点 while curA: if curA is curB: return curA curA curA.next curB curB.next return None题目链接面试题 02.07. 链表相交 - 力扣LeetCode环形链表II题目思路1. 判断是否有环路首先快慢指针一个每次走一步一个每次走两步然后判断是否有一个时刻想等如果想等说明是环路但是注意判断条件当前fast和fast.next因为fast指针一次走两个需要判断下一个是不是空2. 判断环路在哪里成环这里就需要一个数学计算slow x yfast x y n(y z) (n1)速度比 1:22(xy) x y n(y z)求x x (n-1)(yz) z当n 1x z当n1 x n-1圈 z说明x和z一样长说明指针从相遇的地方走到环的开头 和 从head走到环的开头一样长就能 设处一个等式最后得到结果代码#版本一快慢指针法 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def detectCycle(self, head: ListNode) - ListNode: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # If there is a cycle, the slow and fast pointers will eventually meet if slow fast: # Move one of the pointers back to the start of the list slow head while slow ! fast: slow slow.next fast fast.next return slow # If there is no cycle, return None return None题目链接142. 环形链表 II - 力扣LeetCode总结链表就是虚拟头节点很重要其他的就是运用链表的性质来做
