单链表
1. 什么是链表
上图就是一个单链表的结构，链表由不同的节点连接在一起组成的，节点不仅包括值，还有指向下一个结点的指针（记住是指向下一个节点的指针，指针可以理解成下一个节点的引用，即内存地址，这样有了内存地址，我们知道了一个头节点就能找到整个链表），最后一个节点指向一个None。
# 使用python定义一个节点
class ListNode:
def __ini__(self,val=0,next=None):
self.val=val
self.next=next
在大多数情况下，使用头节点（第一个节点）来表示整个链表。 例如，在上面的示例中，头节点是 23。访问第 3 个节点的唯一方法是使用头节点中的“next”字段到达第 2 个节点（节点 6）; 然后使用节点 6 的“next”字段，我们能够访问第 3 个节点。
就比如下面这个方法：
def print_head_value(head: Optional[ListNode]) -> None:
if head is None:
print("The list is empty.")
else:
print("The value of the head node is:", head.val)
刚开始接触链表的时候我也会纳闷，尤其是从java过来的，不知道这个方法的传参怎么传，head: Optional[ListNode]这到底是什么，是传一个结点呢，还是一个链表呢，还是直接传一list。
其实，在链表中头节点不仅表示一个节点，还表示整个链表。
可以通过以下的例子看一下，传入一个[2,4,6,4,9]的列表，是怎么生成一个链表的，其中返回head就包含了整个链表的信息。
def create_linked_list(arr: list) -> Optional[ListNode]:
if not arr:
return None
head = ListNode(arr[0]) # 创建头结点
current = head
for val in arr[1:]: # 遍历数组剩余元素
current.next = ListNode(val) # 为每个元素创建新结点并链接
current = current.next # 移动到下一个结点
return head # 返回头结点
2. 添加操作 - 单链表
可参考leetcode上的图例解释，点击标题链接就到了。
其实，举个例子就是：把一个链表理解成一列火车，把一节装满货物的车厢（结点），连接到一列火车的不同位置（index），如果连接到火车两端的话，只要把链接勾（就是链表指针）挂在别的车厢，或者被别的链接勾挂上就行，如果连接到中间，那既要被后面的车厢链接勾连接，你还要连接前面的车厢。
3.删除操作-单链表
删除就可以理解为，从一列火车上，拆除不需要的车厢下来。特殊的就是拆除车头和车尾稍微有点不同。
4.设计一个链表
每个人的设计可能不一样，我也是弄了好久才跑通所有的案例，其中遇到最多的一个问题就是，在curr.next之前，一定要判断curr是否可能为None
如果自己没思路写不出来，可以直接先拿过去看和理解，不要一直在那里耗着。
# 定义一个节点
class ListNode:
def __init__(self,val=0,next=None):
self.next=next
self.val=val
class MyLinkedList:
# 初始化链表
def __init__(self):
self.head=None
self.size=0
# 获取index位置上的链表节点
def get(self, index: int) -> int:
if index<0 or index>=self.size:
return -1
curr=self.head
# 根据index遍历到该结点
for _ in range(index):
curr=curr.next
if curr is None:
return -1
return curr.val
# 增加值为val的头节点
def addAtHead(self, val: int) -> None:
# 实例化插入的节点
node =ListNode(val)
# 将node下一个节点指向头节点
node.next=self.head
# 将node置为头节点
self.head=node
self.size+=1
# 增加值为val的尾节点
def addAtTail(self, val: int) -> None:
node=ListNode(val)
curr=self.head
if curr is None:
self.head=node
else:
# 当curr.next不为None时,遍历到尾节点
while curr.next:
curr=curr.next
curr.next=node
self.size+=1
# 在索引index位置插入节点
def addAtIndex(self, index: int, val: int) -> None:
if index<0 or index>self.size:
return
node=ListNode(val)
# 当index等于链表长度时，正好需要插入链表的尾节点，这里要直接return掉，不然self.size会多加1
if index==self.size:
self.addAtTail(val)
return
elif index==0:
node.next=self.head
self.head=node
else:
curr=self.head
# 遍历到index的前一位
for _ in range(index-1):
curr=curr.next
# 将node的下一个节点指向原本在index的节点
node.next=curr.next
# 将index的前一位节点指向node,注意上面的和下面的这两个指向不能交换位置执行
curr.next=node
self.size+=1
# 删除索引index处的节点
def deleteAtIndex(self, index: int) -> None:
if index<0 or index>=self.size:
return
prev=None
curr=self.head
if index==0:
self.head=curr.next
else:
# 找出index前一个节点，和index当前节点
for _ in range(index):
prev=curr
curr=curr.next
prev.next=curr.next
self.size-=1
双指针技巧
两种使用双指针技巧的情景：
两个指针从不同位置出发：一个从始端开始，另一个从末端开始； 两个指针以不同速度移动：一个指针快一些，另一个指针慢一些。
在解决环形链表的问题时，经常会用到快慢指针的方法来实现。
下面我们重点讲下，快慢指针的用法。
关于两个指针的速度应该是多少，一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。
当它们相遇时，快指针所走的距离是慢指针所走距离的2倍，记住这个结论，有助于理解快慢指针。你可以理解为，相同时间内，快指针是慢指针速度的两倍，所以距离是两倍。
有了以上的概念让我们直接实战，题目详细介绍，可以点击蓝色标题，直接点击链接查看。
1. 环形链表
题目： 给你一个链表的头节点 head ，判断链表中是否有环。
解题思路： 如果是环形链表，那么快慢指针会相遇，没有相遇就说明不是环形指针
代码：
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
#尽管他们出发的节点不同，但是所用时间相同，因为是慢的走一次快的走一次，所以他们相遇时fast走得距离是慢得的两倍
slow = head
fast = head.next
while slow !=fast:
if not fast or not fast.next:
return False
slow= slow.next
fast=fast.next.next
return True
2. 环形链表II
题目： 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
解题思路： 这个可能比上一个绕一些，看了下面的代码，你可能有些疑惑，不知道为什么要先用快慢指针找到相遇点，然后换成同一速度的指针，将慢指针放回起始节点，重新走，当它们再次重合，就是链表入环的第一个结点。
这个可能需要你用笔来画一下，并且要知道一个前提，刚开始快指针是慢指针所有距离的2倍。
看下图，理解一下，你就懂了。 代码实现：
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 当head为空或head.next为空，环形链表不存在
if not head or not head.next:
return
# 定义快慢两个变量指向head节点
slow = head
fast = head
# 遍历fast
while True:
if not fast or not fast.next:
return None
slow = slow.next
fast = fast.next.next
# 如果它们相等直接跳出
if slow == fast:
break
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
错误代码记录：
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 当head为空或head.next为空，环形链表不存在
if not head or not head.next:
return
# 定义快慢两个变量指向head节点
slow = head
fast = head
# 遍历fast，这里错了，比如当fast为None时，循环跳出，会继续向下运行
# 那么到下一个循环中，当fast.next时就会报错
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 如果它们相等直接跳出
if slow == fast:
break
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
3. 相交链表
题目： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
解题思路： 先计算出两个链表的长度，找到两个链表的长度差，遍历两个链表，让长的链表的指针先走过两个链表的长度差，然后，两个链表的指针再同时走，直到相遇，即为交点。 直接看代码
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
lenA=0
lenB=0
nodeA=headA
nodeB=headB
while nodeA:
lenA+=1
nodeA=nodeA.next
while nodeB:
lenB+=1
nodeB=nodeB.next
if lenA>lenB:
for _ in range(lenA-lenB):
headA=headA.next
elif lenB>lenA:
for _ in range(lenB-lenA):
headB=headB.next
while headA!=headB:
headA=headA.next
headB=headB.next
return headA
提示
在调用 next 字段之前，始终检查节点是否为空。 获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。 仔细定义循环的结束条件。 运行几个示例，以确保你的结束条件不会导致无限循环。在定义结束条件时，你必须考虑我们的第一点提示。
4. 删除链表倒数第N个结点
题目： 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
解题思路一： 先计算出链表的长度，然后使用长度减去n+1，得到要删除结点的前一位，通过该结点前一位指向该结点的下一位，实现删除该结点。需注意链表长度为1和链表长度相等的情况。 该方法的缺点是需要执行2次遍历遍历操作，一次是计算链表长度，一次是找到要删除结点的前一位结点。
代码实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
node=head
length=0
# 计算链表的长度
while node:
length+=1
node=node.next
curr=head
if length return head elif length==n: head=head.next return head else: # 获取删除结点的前一位 for _ in range(length-n-1): curr=curr.next # 通过上面的条件判断之后，到这里curr的长度至少等于2，所以不用担心curr或curr.next等于None curr.next=curr.next.next return head 解题思路二： 使用双指针的思路，实现扫描一遍即可实现该功能。 首先让快指针和慢指针相差n个节点，然后同时移动快指针和慢指针，直到快指针到达链表末尾，此时慢指针就在要删除的第n个结点的前一位。 为什么会有这样的情况，因为始终快指针与慢指针相差n个结点，那么当快指针到达链表结尾的时候，慢指针也是和快指针相差n个结点，那慢指针的位置就能确定在删除节结点的前一位。 代码： class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: # 定义两个指针 first = head second = head # 将第一个指针向前移动 n+1 步 for _ in range(n + 1): if first is None: # 如果链表长度不足 n+1，则直接返回头结点的下一个节点 return head.next first = first.next # 移动第一个和第二个指针直到第一个指针到达链表尾部 while first is not None: first = first.next second = second.next # 删除倒数第 n 个节点,这里不用担心second 或 second.next为None,因为上面的for循环保证second在first之后n+1个，n+1>2 second.next = second.next.next return head 复杂度分析 点击链接，看双指针的小结 本文参考，leetcode网站上的LeetBook，详见页面：https://leetcode.cn/leetbook/read/linked-list/x6ybqh/ 推荐文章
发表评论