2.链表(代码随想录——python版本)
2.链表(代码随想录——python版本)
链表的概念:
链表是由指针串联在一起的线性结构,一个节点(node)由两部分组成:
- 数据域——用来存储数据;
- 指针域——用来指向下一个节点(如果是双指针,另一个指向前一个结点),最后一个节点的指针指向null(空)。
链表的入口节点称为链表的头节点。
我们发现,在Python中是没有链表这样的数据类型的,所以我们需要自己定义链表类:
class listnode(object):
# 这是一个单链表类型。
def __init__(self,num = 0, next = None):
self.num = num
self.next = next
如果我们建立了一个链表节点head,并将其赋值给了tmp,那么它们操作的便是同一份链表,tmp对链表的操作也会影响到head对链表的访问。
链表的类型:
单链表:
上文所写的就是单链表。
双链表:
每一个node有两个指针,一个指向前node一个指向后node,可以向前查找也可以向后查找。(单链表只能够向后查找)。
循环列表:
链表的首尾相连,用来解决约瑟夫环问题。
链表的存储:
与数组不同,其内存空间并不是连续的,只是靠着指针将它们结合起来。(也就是说物理上是不连续的仅仅在逻辑上连续)。
基础操作:
删除一个节点:
找到要删除的节点的前一个节点,将next指向后一个节点即可。(python中有自己的内存回收机制,不用我们手动去回收,单要是C++的话是需要的。)
class listnode(object):
def __init__(self, num, next=None):
self.num = num
self.next = next
head = listnode(1)
head.next = listnode(2)
head.next.next = listnode(3)
print(head.num,head.next.num,head.next.next.num,head.next.next.next)
head.next = head.next.next
print(head.num,head.next.num,head.next.next)
下面我们试着将其封装一个函数:
203. 移除链表元素 - 力扣(LeetCode)
不设置虚拟节点(不建议那么写,因为真的很麻烦。。。特别是判断head是否为空需要判断多次,我将错误代码也附加在下面,代码随想录中并没有这样的实现,若有更好的想法欢迎交流):
思路:
- 首先,判断head是否为空,若为空,直接返回head;
- 然后判断head是否需要删除,若需要,将head变为head的后一个节点:
- 如果更新后的head为空,一定要及时退出,不然会报我下面贴出来的错误。
- 然后创建一个tmp,指向head,由于已经保证了head不会再被删除,所以直接比较tmp.next.val的值就可以了,若要删除,将tmp.next的值更新为tmp.next.next;否则,tmp变为tmp.next,为下一次循环做准备。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if head == None:
return head
else:
# 先考虑头节点位置怎么删除
while head.val == val:
head = head.next
tmp = head
while tmp.next:
# 现在我们其实已经确保了起始位置的val不会是val了
if tmp.next.val == val:
tmp.next = tmp.next.next
else:
tmp = tmp.next
return head
报错信息如下:
AttributeError: 'NoneType' object has no attribute 'val'
^^^^^^^^
while head.val == val:
Line 12 in removeElements (Solution.py)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ret = Solution().removeElements(param_1, param_2)
Line 54 in _driver (Solution.py)
_driver()
Line 69 in <module> (Solution.py)
正确的代码:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if head == None:
return head
else:
# 先考虑头节点位置怎么删除
while head.val == val:
head = head.next
if head == None:
return head
tmp = head
while tmp.next:
# 现在我们其实已经确保了起始位置的val不会是val了
if tmp.next.val == val:
tmp.next = tmp.next.next
else:
tmp = tmp.next
return head
设置一个虚节点:
设置一个虚节点,让我们可以使用一个相同的规则去删除节点。
这是怎么做到的呢,我们创建一个虚拟的头节点,dummy_node其next指向head,这样我们的所有删除都是和上文删除tmp一样的了,需要注意的是返回的值应该为dummy_node.next。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# 建立一个临时的虚拟头节点
tmp_head = ListNode(next = head)
# current为循环要用的,为什么不直接用tmp_head,因为我们要返回新的头节点,不应该变动虚拟头节点的位置,current指向的也是和虚拟头节点指向的链表
current = tmp_head
while current.next != None:
# 为什么直接比较next.val的值呢,因为最开始的位置是虚拟头节点而不是头节点
if current.next.val == val:
# 指向原来节点的后一个节点的
current.next = current.next.next
else:
# 将当前节点变为下一个节点,为循环做准备
current = current.next
# 返回虚拟头节点的next指向就是新的头节点
return tmp_head.next
小结:
- 虚拟节点的概念!
增加一个节点:
创建一个节点然后将要插入部位的前一个node的next指向它,它的next指向原位置的元素。
我们可以发现如果我们在head处插入是非常方便的O(1),要是想要从末尾添加一个node则需要先遍历原链表一次才能够实现,这是非常麻烦的O(n)。
这里不给出代码啦,因为下面的题目会全部写一遍~
设计一个链表:
707. 设计链表 - 力扣(LeetCode)
链表类(节点类):
class ListNode:
def __init__(self,val = 0, next = None):
self.val = val
self.next = next
MyLinkedList类:
class MyLinkedList:
def __init__(self):
# 先需要创建一个虚拟头节点:
self.dummy_head = ListNode()
self.size = 0
def get(self, index: int) -> int:
def addAtHead(self, val: int) -> None:
self.dummy_head.next = ListNode(val, self.dummy_head.next)
size += 1
def addAtTail(self, val: int) -> None:
def addAtIndex(self, index: int, val: int) -> None:
def deleteAtIndex(self, index: int) -> None:
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
反转链表:
206. 反转链表 - 力扣(LeetCode)
双指针:
设定两个指针,pre表示前一个节点,cur表示当前节点;将pre初始化为None,cur初始化为head;cur和pre一起向前移动,这样就能一直更改指向顺序实现反向,但是我们发现,如果更改完顺序后,我们没有办法遍历原链表的顺序了,所以要使用tmp变量去暂存cur.next的值。
# 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]:
pre = None
cur = head
while cur:
# 由于我们之后要将cur后的next反向,所以要在赋值前将cur.next的值保存下来
tmp = cur.next
# 将cur指向pre(前一个节点)
cur.next = pre
# 更新pre和cur的位置
pre, cur = cur, tmp
# 返回pre(即为头节点)
return pre
递归:
思路还是双指针。
# 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]:
# 定义递归
def recur(cur, pre):
# 和双指针法一样,指定当cur为None为退出条件
if cur == None: return pre
else:
# 一样需要记录cur.next
tmp = cur.next
cur.next = pre
# 记住一定要return否则程序运行会有问题,在新一轮递归中,tmp为cur,pre为cur
return recur(tmp, cur)
return recur(head, None)
小结:
- 要牢记双指针(改变顺寻,交换);
- 递归的运用。
两两交换链表的节点:
24. 两两交换链表中的节点 - 力扣(LeetCode)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(next = head)
# cur和dummy_head指向的是同一个链表
cur = dummy_head
# 保证至少还有两个元素在链表内
while cur.next and cur.next.next:
# 暂存第一个节点,因为会改变虚拟节点的指向
tmp1 = cur.next
# 暂存第三个节点,因为会改变第二个节点的指向
tmp2 = cur.next.next.next
cur.next, cur.next.next,cur.next.next.next = cur.next.next,tmp1,tmp2
cur = cur.next.next
return dummy_head.next
小结:
- 要注意循环结束的条件;
- 画图进行交换的分析,确定哪些节点需要暂存起来
删除链表中的倒数第n个节点:
19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
关键在于找到倒数第n个节点的位置在哪,要删除倒数第n个节点,那么操作指针要指向上一个节点。
方法:
使用虚拟头节点(不需要对操作的节点是不是头节点进行特殊操作);使用双指针法,两个指针先都指向dummy_head,让快指针先移动n步,然后再让快慢指针一起移动,直到快指针指向了None处,慢指针就找到了倒数第n个,此时慢指针便找到了倒数第n个节点的位置,但我们要做的是删除,所以快指针应该先走n+1步。
# 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]:
dummy_node = ListNode(next = head)
fast = dummy_node
slow = dummy_node
for i in range(n+1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy_node.next
- 双指针法(倒数第n,交换,反序);
- 难点在于如何找到倒数第n个元素在哪,让快指针比慢指针先走n步,慢指针所在的位置就是倒数第n个节点的位置;
- 清楚删除节点是要找到删除节点的前一个元素。
链表相交:
面试题 02.07. 链表相交 - 力扣(LeetCode)
说实话本来以为就是遍历链表找到值相同的就能够返回了,但没想到居然是找节点相同的(虽然还是没搞明白示例的1为什么不对,但看下面评论貌似是被给定的值给限制死了,但是代码里也没有体现啊喂,而且先给出图再问有没有相交是否有点。。。)
首先循环遍历两个链表,得出两个链表的长度,然后找出较长的那一端,将其指针往后挪动多的长度的位数,这样之后,curA和curB就可以一起进行移动,并判断是否相等了,只要curA==curB(指针域相同,数值域也相同,就认为找到交点了)。写的有点啰嗦,实则可以进行优化,可以优化的部分注明在下面的代码中。
# 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:
curA = headA
curB = headB
lenA, lenB = 0, 0
while curA:
curA = curA.next
lenA += 1
while curB:
curB = curB.next
lenB += 1
curA, curB = headA, headB
# 这边是可以优化的,写成lenA<lenB然后将lenA,lenB以及curA和curB互换位置,之后的代码便都是一样的了。
if lenA >= lenB:
x = lenA - lenB
for i in range(x):
curA = curA.next
while curA:
if curA == curB:
return curA
else:
curA, curB = curA.next,curB.next
else:
x = lenB - lenA
for i in range(x):
curB = curB.next
while curA:
if curA == curB:
return curA
else:
curA, curB = curA.next,curB.next
return None
环形列表:
142. 环形链表 II - 力扣(LeetCode)
题目要求比较多,不仅要判断是不是环形还要判断入口在哪,说实话有种无从落笔的感觉。。。
判断是不是环形:
首先,我们使用双指针法(实话,没想到,看了随想录的视频讲解才明白)。设定快慢指针都指向头节点,然后,让慢节点一个节点一个节点的更新,快节点则以两个节点的速度更新(在环上就是以一个节点的速度接近慢节点,以免丢失)。同时需要对快节点和其下一个节点是否为空进行判断,若是空说明不是环,直接退出;若有节点则继续,由于循环次数不固定,所以使用while循环。
判断入口在哪:
这是一个数学问题,首先设定head到节点的长度为x,快慢节点相遇的位置慢节点顺时针走过的距离为y,剩下的圆环路径值为z;慢指针走过的长度为x+y;快指针走过的长度为x+y+n(y+z);
由于快指针的速度是慢指针的两倍:
2(x+y) = x+y+n(y+z)——>x = (n-1)(y+z)+z
从这个式子我们好像得不出说明东西,那我们让n=1,发现x = z,让n=2,发现 x = y+z +z;规律就是一定会走过一个z和n-1个环的长度和x是一样的,那么将一个指针挪回head,另一个指针停留在原位置,以一个单位的速度一起往后移动,相遇的位置就是入口。
为什么慢指针走不了一圈呢?
假设在进入时,两个指针都在起点位置,过了一圈,那么快慢指针刚好会在入口位置相遇,这样最远的位置都只有一圈,其他位置就更不用说了。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 双指针法
fast,slow = head, head
# 判断当前快指针和快指针的下一个节点是否存在,若不存在说明不存在环
while fast and fast.next:
# 慢指针以1个单位的速度前进
slow = slow.next
# 快指针以两个单位的速度前进,即以一个单位的速度逼近快指针,保证不会错过慢指针
fast = fast.next.next
# 若两个相遇了,说明存在环
if fast == slow:
# x = n (y + z) - y == (n-1)(y+z) + z——
# x为起点到入口的距离,y为慢指针走过的环的距离(不到一圈),z为剩余的环的距离
# 将其中的一个指针挪到起点,另一个保留在原位置,都以一个单位的速度前进直至相遇
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
# 返回相遇点,就是入口
return slow
return None
小结:
- 对快慢指针的认识还是太浅了;
- 对如何判断环有了基本认识;
- 感觉链表问题基本都是双指针问题。
链表小结:
- 虚拟头节点的方法很常用,需要牢记;
- 链表的许多问题都可以转换为双指针问题,没有思路的时候可以试试;
- 将head赋值给多给不同的指针,这些指针操作的都是一个链表;
- 创建节点时能够一步到位就一步到位,不要太啰嗦(我容易犯的毛病)
过完第一遍感觉只是有了一个大致的印象,后面好像代码随想录会有双指针法的专栏,依然会坚持学习的。估计可能会5-6刷整个代码随想录(后期熟练之后刷题应该会很快,毕竟我才研0还有很多时间~)