算法题 链表系列
1. Dummy Head#
链表 A B C, 我们若想移除 B, 需要 A.next = B.next, 所以当头部节点也有可能被移除的时候, 我们就需要一个 dummy 节点: D A B C, 从而实现 D.next = A.next 进而删除 A 节点,
除此之外, 我们并不能直接移动 dummy 节点, 因为我们要记住 头部节点的位置, 用于函数返回, 不管这个头部 是 A, B 或者 C,
我们要再使用一个节点 current, 通过 current = current.next 来遍历整个链表, 这样不管最后怎么变, dummy.next 都是最后形成的链表的第一个节点,
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeElements(self, head, val):
# 用于记住头部节点
dummy = ListNode(0, head)
current = dummy
while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy.next
2. 交叉点#
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
ta, tb = headA, headB
while ta != tb:
ta = ta.next if ta else headB
tb = tb.next if tb else headA
return tb
ta = ta.next if ta else headB
并不会报错, 即使 ta
为 None, 因为这语句先执行 if ta
, 所以不会出现, None 不存在 next 属性的异常,
3. 实现链表#
在做涉及到 index 和 size 相关的问题时, 一定要考虑清楚, index 是从 0 开始 还是从 1 开始, 这很重要, 它告诉了我们 index 是不是 可以等于 size, 还是 size = index + 1
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.head = None
self.size = 0
def get(self, index):
if index < 0 or index >= self.size:
return -1
cur = self.head
for _ in range(index):
cur = cur.next
return cur.val
def addAtHead(self, val):
# self.head 只是一个 reference, 指向在堆上的对象,
# 只有有引用指向对象, 对象就不会被清理
# 这也是为什么我们可以这么操作
node = Node(val, self.head)
self.head = node
self.size += 1 # 更新长度
def addAtTail(self, val):
# 链表相关的题, 每当访问某个节点的 next,
# 就要想一下, 该节点有没有可能为空
if not self.head:
self.head = Node(val)
else:
cur = self.head
while cur.next:
cur = cur.next
cur.next = Node(val)
self.size += 1 # 更新长度
def addAtIndex(self, index, val):
if index > self.size:
return # 超出范围,直接返回
if index <= 0:
self.addAtHead(val)
return
dummy = Node(0, self.head)
cur = dummy
for _ in range(index):
cur = cur.next
node = Node(val, cur.next)
cur.next = node
self.head = dummy.next
self.size += 1 # 更新长度
def deleteAtIndex(self, index):
if index < 0 or index >= self.size:
return # 超出范围,直接返回
dummy = Node(0, self.head)
cur = dummy
for _ in range(index):
cur = cur.next
cur.next = cur.next.next
self.head = dummy.next
self.size -= 1 # 更新长度
用到了 prev 和 head, 即每次交换都是 prev 和 head 往下移动, 前者代表虚拟节点, 后者代表要交换的第一个,
first 和 second 则代表两个要交换的节点, 这样 prev first second 三个配合交换, 交换之后, prev 往下移动, head 往下移动, 继续重复
def swapPairs(self, head):
if not head:
return None
if not head.next:
return head
dummy = ListNode(0)
dummy.next = head
prev = dummy
while head and head.next:
first = head
second = head.next
prev.next = second
first.next = second.next
second.next = first
prev = first
head = first.next
return dummy.next
查看其他文章