2.链表（代码随想录——python版本）

2.链表（代码随想录——python版本）

链表的概念：

链表是由指针串联在一起的线性结构，一个节点（node）由两部分组成：

• 数据域——用来存储数据；
• 指针域——用来指向下一个节点（如果是双指针，另一个指向前一个结点），最后一个节点的指针指向null（空）。

链表的入口节点称为链表的头节点。

我们发现，在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++的话是需要的。）

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，为下一次循环做准备。

# 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。

# 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）

链表类（节点类）：

class ListNode:def __init__(self,val = 0, next = None):self.val = valself.next = next

MyLinkedList类：

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的值。

# 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

递归：

思路还是双指针。

# 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）

# 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步。

# 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（指针域相同，数值域也相同，就认为找到交点了）。写的有点啰嗦，实则可以进行优化，可以优化的部分注明在下面的代码中。

# 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，另一个指针停留在原位置，以一个单位的速度一起往后移动，相遇的位置就是入口。

为什么慢指针走不了一圈呢？

​ 假设在进入时，两个指针都在起点位置，过了一圈，那么快慢指针刚好会在入口位置相遇，这样最远的位置都只有一圈，其他位置就更不用说了。

# 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还有很多时间~）