二刷力扣--链表

链表

链表类型：
单链表（可以访问后面的一个节点）
双链表（可以访问前后节点）
循环链表（最后一个节点指向首节点）

在Python中定义单链表节点：

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

移除链表元素 203.

#链表删除 #哑节点
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

为了统一处理删除操作，在head节点前添加一个哑节点。

class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:dummy = ListNode(0, head)pre = dummycur = dummy.nextwhile cur:if cur.val == val:pre.next = cur.next cur = cur.nextelse:pre = pre.nextcur = cur.nextreturn dummy.next

Python有垃圾回收，不需要手动删除节点。

设计链表 707.

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

class Node:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:def __init__(self):self.dummy = Node(-1, None)self.max_index = -1  def get(self, index: int) -> int:if index < 0 or index > self.max_index:return -1cur = self.dummy.next for  i in range(index):cur = cur.nextreturn cur.valdef addAtHead(self, val: int) -> None:self.dummy.next  = Node(val, self.dummy.next)self.max_index += 1def addAtTail(self, val: int) -> None:cur = self.dummywhile cur.next:cur = cur.nextcur.next = Node(val)self.max_index += 1def addAtIndex(self, index: int, val: int) -> None:if  index < 0 or index > self.max_index + 1:return cur = self.dummyi = 0for i in range(index):cur = cur.nextcur.next = Node(val, cur.next)self.max_index += 1def deleteAtIndex(self, index: int) -> None:if  index < 0 or index > self.max_index:return cur = self.dummyfor i in range(index):cur = cur.nextcur.next = cur.next.next self.max_index -= 1

反转链表 206.

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
#双指针

使用temp保存cur.next ，因为反转后cur.next就改变了，无法再访问原来的下一个元素了。

class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:pre = Nonecur = headwhile cur:temp = cur.next # 下一个节点cur.next  = pre # 反转next方向pre = curcur = temp # 去下一个return pre 

两两交换链表中的节点 24.

#哑节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

有些题解里很多cur.next.next.next，看起来很麻烦。 用临时节点记录一下似乎就不用那么多next了。而且也不用考虑.next赋值的顺序了。

class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:dummy = ListNode(0, head)cur = dummy# 交换cur后面的两个节点while cur.next and cur.next.next:node1 = cur.next        node2 = node1.next  node3 = node2.next  #  cur->node1->node2-->node3(node2.next)  ----> cur->node2->node1-->node3(node2.next)  cur.next = node2  node2.next = node1 node1.next = node3cur = node1 return dummy.next

删除链表的倒数第N个节点 19.

#双指针 #哑节点
双指针的应用。快指针fast先走n步，当快指针到达倒数第1个节点时，慢指针slow到达倒数n+1个节点，删除slow的下一个节点。
哑节点对简化删除操作很有用，如果不用哑节点，删除head就要特殊处理。

class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy = ListNode(0, head)fast = dummyslow = dummy# 当fast 到达倒数第1个节点， slow到达倒数第n+1个节点for i in range(n):fast = fast.nextwhile fast.next :fast = fast.nextslow = slow.nextslow.next = slow.next.next return dummy.next 

链表相交 面试题 02.07. 同 160

#双指针
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

两个链表如果有相同的节点，则从相同节点开始，一直到末尾都是相同的。
让较长的链表先走 abs(lengthA-lengthB)个节点，然后比较两个链表。

class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:def getLength(head):length = 0while head:head = head.nextlength += 1return lengthlengthA = getLength(headA)lengthB = getLength(headB) Long, Short = (headA, headB) if lengthA > lengthB  else (headB, headA)for _ in range (abs(lengthA- lengthB)):Long = Long.nextwhile Short:if Short == Long:return Shortelse:Short = Short.nextLong = Long.nextreturn None

环形链表II 142.

#集合 #双指针

1. 直接用set记录访问过的节点，再次遇到则表明出现了环。

class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:visited = set()pos = headwhile pos:if  pos in visited:return poselse:visited.add(pos)pos = pos.nextreturn None

2. 双指针。快指针fast一次走两步，慢指针slow一次走一步。如果有环，两个指针一定会遇到。
   而找到环的入口比较难，需要推导一下。（这个不太好理解，推荐看代码随想录的视频）
   

相遇时，slow指针走过的节点数是 x+y, fast走过的节点数是 x+y+ n(y+z) ,n>=1
fast一次走两个节点，所以走过的节点数是slow的两倍，即 x+y+n(y+z) = 2（x+y)。 化简一下，得到 x = (n-1)(y+z) + z
n = 1时， x = z 也就是说，一个指针index1从slow与fast相遇点出发，一个指针index2从头节点出发，会在入口节点相遇。

n大于1时和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点

class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:fast = headslow = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:index1 = fastindex2 = headwhile index1 != index2:index1 = index1.nextindex2 = index2.nextreturn index2return None

链表小结

哑节点对简化链表操作很有用。添加一个哑节点，对头节点的处理会和其他节点一样。
双指针是常用的方法，可以用来判断链表是否有环，找到链表倒数第n个元素。