python_0">2.链表(代码随想录——python版本)
链表的概念:
链表是由指针串联在一起的线性结构,一个节点(node)由两部分组成:
- 数据域——用来存储数据;
- 指针域——用来指向下一个节点(如果是双指针,另一个指向前一个结点),最后一个节点的指针指向null(空)。
我们发现,在Python中是没有链表这样的数据类型的,所以我们需要自己定义链表类:
python">class listnode(object):# 这是一个单链表类型。def __init__(self,num = 0, next = None):self.num = numself.next = next
如果我们建立了一个链表节点head,并将其赋值给了tmp,那么它们操作的便是同一份链表,tmp对链表的操作也会影响到head对链表的访问。
链表的类型:
单链表:
上文所写的就是单链表。
双链表:
每一个node有两个指针,一个指向前node一个指向后node,可以向前查找也可以向后查找。(单链表只能够向后查找)。
循环列表:
链表的首尾相连,用来解决约瑟夫环问题。
链表的存储:
与数组不同,其内存空间并不是连续的,只是靠着指针将它们结合起来。(也就是说物理上是不连续的仅仅在逻辑上连续)。
基础操作:
删除一个节点:
找到要删除的节点的前一个节点,将next指向后一个节点即可。(python中有自己的内存回收机制,不用我们手动去回收,单要是C++的话是需要的。)
python">class listnode(object):def __init__(self, num, next=None):self.num = numself.next = nexthead = 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,为下一次循环做准备。
python"># 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 headelse:# 先考虑头节点位置怎么删除while head.val == val:head = head.nexttmp = headwhile tmp.next:# 现在我们其实已经确保了起始位置的val不会是val了if tmp.next.val == val:tmp.next = tmp.next.nextelse:tmp = tmp.nextreturn 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 headelse:# 先考虑头节点位置怎么删除while head.val == val:head = head.nextif head == None:return headtmp = headwhile tmp.next:# 现在我们其实已经确保了起始位置的val不会是val了if tmp.next.val == val:tmp.next = tmp.next.nextelse:tmp = tmp.nextreturn head
设置一个虚节点:
设置一个虚节点,让我们可以使用一个相同的规则去删除节点。
这是怎么做到的呢,我们创建一个虚拟的头节点,dummy_node其next指向head,这样我们的所有删除都是和上文删除tmp一样的了,需要注意的是返回的值应该为dummy_node.next。
python"># 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_headwhile current.next != None:# 为什么直接比较next.val的值呢,因为最开始的位置是虚拟头节点而不是头节点if current.next.val == val:# 指向原来节点的后一个节点的current.next = current.next.nextelse:# 将当前节点变为下一个节点,为循环做准备current = current.next# 返回虚拟头节点的next指向就是新的头节点return tmp_head.next
小结:
- 虚拟节点的概念!
增加一个节点:
创建一个节点然后将要插入部位的前一个node的next指向它,它的next指向原位置的元素。
我们可以发现如果我们在head处插入是非常方便的O(1),要是想要从末尾添加一个node则需要先遍历原链表一次才能够实现,这是非常麻烦的O(n)。
这里不给出代码啦,因为下面的题目会全部写一遍~
设计一个链表:
707. 设计链表 - 力扣(LeetCode)
链表类(节点类):
python">class ListNode:def __init__(self,val = 0, next = None):self.val = valself.next = next
MyLinkedList类:
python">class MyLinkedList:def __init__(self):# 先需要创建一个虚拟头节点:self.dummy_head = ListNode()self.size = 0def get(self, index: int) -> int:def addAtHead(self, val: int) -> None:self.dummy_head.next = ListNode(val, self.dummy_head.next)size += 1def 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的值。
python"># 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 = Nonecur = headwhile cur:# 由于我们之后要将cur后的next反向,所以要在赋值前将cur.next的值保存下来tmp = cur.next# 将cur指向pre(前一个节点)cur.next = pre# 更新pre和cur的位置pre, cur = cur, tmp# 返回pre(即为头节点)return pre
递归:
思路还是双指针。
python"># 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 preelse:# 一样需要记录cur.nexttmp = cur.nextcur.next = pre# 记住一定要return否则程序运行会有问题,在新一轮递归中,tmp为cur,pre为curreturn recur(tmp, cur)return recur(head, None)
小结:
- 要牢记双指针(改变顺寻,交换);
- 递归的运用。
两两交换链表的节点:
24. 两两交换链表中的节点 - 力扣(LeetCode)
python"># 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.nextcur.next, cur.next.next,cur.next.next.next = cur.next.next,tmp1,tmp2cur = cur.next.nextreturn dummy_head.next
小结:
- 要注意循环结束的条件;
- 画图进行交换的分析,确定哪些节点需要暂存起来
删除链表中的倒数第n个节点:
19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
关键在于找到倒数第n个节点的位置在哪,要删除倒数第n个节点,那么操作指针要指向上一个节点。
方法:
使用虚拟头节点(不需要对操作的节点是不是头节点进行特殊操作);使用双指针法,两个指针先都指向dummy_head,让快指针先移动n步,然后再让快慢指针一起移动,直到快指针指向了None处,慢指针就找到了倒数第n个,此时慢指针便找到了倒数第n个节点的位置,但我们要做的是删除,所以快指针应该先走n+1步。
python"># 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_nodeslow = dummy_nodefor i in range(n+1):fast = fast.nextwhile fast:fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn dummy_node.next
- 双指针法(倒数第n,交换,反序);
- 难点在于如何找到倒数第n个元素在哪,让快指针比慢指针先走n步,慢指针所在的位置就是倒数第n个节点的位置;
- 清楚删除节点是要找到删除节点的前一个元素。
链表相交:
面试题 02.07. 链表相交 - 力扣(LeetCode)
说实话本来以为就是遍历链表找到值相同的就能够返回了,但没想到居然是找节点相同的(虽然还是没搞明白示例的1为什么不对,但看下面评论貌似是被给定的值给限制死了,但是代码里也没有体现啊喂,而且先给出图再问有没有相交是否有点。。。)
首先循环遍历两个链表,得出两个链表的长度,然后找出较长的那一端,将其指针往后挪动多的长度的位数,这样之后,curA和curB就可以一起进行移动,并判断是否相等了,只要curA==curB(指针域相同,数值域也相同,就认为找到交点了)。写的有点啰嗦,实则可以进行优化,可以优化的部分注明在下面的代码中。
python"># Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:curA = headAcurB = headBlenA, lenB = 0, 0while curA:curA = curA.nextlenA += 1while curB:curB = curB.nextlenB += 1curA, curB = headA, headB# 这边是可以优化的,写成lenA<lenB然后将lenA,lenB以及curA和curB互换位置,之后的代码便都是一样的了。if lenA >= lenB:x = lenA - lenBfor i in range(x):curA = curA.nextwhile curA:if curA == curB:return curAelse:curA, curB = curA.next,curB.nextelse:x = lenB - lenAfor i in range(x):curB = curB.nextwhile curA:if curA == curB:return curAelse:curA, curB = curA.next,curB.nextreturn 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,另一个指针停留在原位置,以一个单位的速度一起往后移动,相遇的位置就是入口。
为什么慢指针走不了一圈呢?
假设在进入时,两个指针都在起点位置,过了一圈,那么快慢指针刚好会在入口位置相遇,这样最远的位置都只有一圈,其他位置就更不用说了。
python"># Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass 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 = headwhile slow != fast:slow = slow.nextfast = fast.next# 返回相遇点,就是入口return slowreturn None
小结:
- 对快慢指针的认识还是太浅了;
- 对如何判断环有了基本认识;
- 感觉链表问题基本都是双指针问题。
链表小结:
- 虚拟头节点的方法很常用,需要牢记;
- 链表的许多问题都可以转换为双指针问题,没有思路的时候可以试试;
- 将head赋值给多给不同的指针,这些指针操作的都是一个链表;
- 创建节点时能够一步到位就一步到位,不要太啰嗦(我容易犯的毛病)
过完第一遍感觉只是有了一个大致的印象,后面好像代码随想录会有双指针法的专栏,依然会坚持学习的。估计可能会5-6刷整个代码随想录(后期熟练之后刷题应该会很快,毕竟我才研0还有很多时间~)