链表
链表类型：
单链表（可以访问后面的一个节点）
双链表（可以访问前后节点）
循环链表（最后一个节点指向首节点）
在Python中定义单链表节点：
class ListNode: def __init__(self, val, next=None): self.val = val self.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 = dummy cur = dummy.next while cur: if cur.val == val: pre.next = cur.next cur = cur.next else: pre = pre.next cur = cur.next return dummy.next
Python有垃圾回收，不需要手动删除节点。
设计链表 707.
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
class Node: def __init__(self, val=0, next=None): self.val = val self.next = next class 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 -1 cur = self.dummy.next for i in range(index): cur = cur.next return cur.val def addAtHead(self, val: int) -> None: self.dummy.next = Node(val, self.dummy.next) self.max_index += 1 def addAtTail(self, val: int) -> None: cur = self.dummy while cur.next: cur = cur.next cur.next = Node(val) self.max_index += 1 def addAtIndex(self, index: int, val: int) -> None: if index < 0 or index > self.max_index + 1: return cur = self.dummy i = 0 for i in range(index): cur = cur.next cur.next = Node(val, cur.next) self.max_index += 1 def deleteAtIndex(self, index: int) -> None: if index < 0 or index > self.max_index: return cur = self.dummy for i in range(index): cur = cur.next cur.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 = None cur = head while cur: temp = cur.next # 下一个节点 cur.next = pre # 反转next方向 pre = cur cur = 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 = node3 cur = 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 = dummy slow = dummy # 当fast 到达倒数第1个节点， slow到达倒数第n+1个节点 for i in range(n): fast = fast.next while fast.next : fast = fast.next slow = slow.next slow.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 = 0 while head: head = head.next length += 1 return length lengthA = getLength(headA) lengthB = getLength(headB) Long, Short = (headA, headB) if lengthA > lengthB else (headB, headA) for _ in range (abs(lengthA- lengthB)): Long = Long.next while Short: if Short == Long: return Short else: Short = Short.next Long = Long.next return None
环形链表II 142.
#集合 #双指针
- 直接用
set记录访问过的节点，再次遇到则表明出现了环。
cla
双指针。快指针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 = head slow = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: index1 = fast index2 = head while index1 != index2: index1 = index1.next index2 = index2.next return index2 return None
链表小结
哑节点对简化链表操作很有用。添加一个哑节点，对头节点的处理会和其他节点一样。
双指针是常用的方法，可以用来判断链表是否有环，找到链表倒数第n个元素。
