day3-渐渐明白[链表]的边界_阿琛与树的博客-爱代码爱编程
代码随想录算法训练营Day3
链表理论基础
链表是通过指针串联在一起的数据结构.链表的入口处被称为head.
单链表:每个节点由两部分组成,一个是数据域,一个是指针域,(存放指向下一个节点的指针),最后一个节点的指针域指向null.(单链表中的指针域只指向节点的下一个节点.)
双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点.(双链表 既可以向前查询也可以向后查询.)
循环链表: 单链表的最后一个节点指针指向head.
数组是在内存中是连续分布的,但是链表在内存中不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的 ,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。
leetcode把链表默认定义好了,**面试时,注意如何定义链表.**删除节点在C++中,要手动释放节点.
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
链表的增添和删除都是O(1)操作,也不会影响到其他节点.
注意: 链表中删除头节点: head = head.next
;链表中删除中间节点: node3.next = node5
(node4
被删除).
增加虚拟头结点 dummyHead
可以把两种删除方法统一处理.
性能分析
插入/删除TC | 查询TC | 适用场景 | |
---|---|---|---|
数组 | O(N) | O(1) | 数据量固定*,较少增减,频繁查询 |
链表 | O(1) | O(N) | 数据量不固定,频繁增减,较少查询 |
*: 数组在定义的时候,长度就是固定的,如果想改动数组的长度,就需要重新定义一个新的数组。
203, 移除链表元素
方法一:递归
链表具有天然的递归性。可以将原链表看成头结点后挂着,一个更短的链表.
方法二: 迭代
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# 递归
# if head == None:
# return
# head.next = self.removeElements(head.next, val)
# return head.next if head.val == val else head
# TC:O(N)
# SC:O(1)
# 迭代
while head and head.val == val:
head = head.next
cur = head
while cur.next and cur:
if cur.next.val == val:
cur.next = pre.next.next
else:
cur = pre.next
return head
法三: 虚拟头节点方法
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy_head = ListNode(next=head) #添加一个虚拟节点
cur = dummy_head
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next #删除cur.next节点
else:
cur = cur.next
return dummy_head.next
cur = head 且 从cur
开始,使用cur.next
的原因是,单向链表没有办法回溯上一节点,我们删除cur.next
,还可以简单的回到cur
.
707.设计链表
提示是使用虚拟头结点.
# 单链表
class Node:
def __init__(self, val):
self.val = val
self.next = None
class MyLinkedList:
def __init__(self):
self.head = Node(0) # 虚拟头部节点
self.size = 0 # 节点数
def get(self, index: int) -> int:
if index >= self.size:
return -1
cur = self.head
for _ in range(index+1):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.size, val)
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return None
self.size += 1
cur = self.head
for _ in range(index):
cur = cur.next
newNode = Node(val)
newNode.next = cur.next
cur.next = newNode
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
self.size -= 1
cur = self.head
for _ in range(index):
cur = cur.next
# print(cur.val)
# print("111111111")
if cur.next:
cur.next =cur.next.next
else:
cur.next = None
再实现一遍双链表
206.反转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 双指针 double pointers
# 迭代就是循环,双指针也套在循环里
# pre = None
# cur = head
# while cur: # 注意此处结束的终止条件
# tem = cur.next
# cur.next = pre
# pre =cur
# cur =tem
# return pre
# TC: O(N)
# SC: O(1)
# 递归
def reverse(pre,cur):
if not cur:
return pre
tem = cur.next
cur.next = pre
return reverse(cur, tem)
return reverse(None, head) # Initalization
#注意 结束后返回的是pre,而不是head