链表

1. 找中间节点的题目 2. 链表逆序 3. 多处修改引用 4. 链表相交&环技巧经典题目

1. 找中间节点的题目

找中间节点题目只有一种套路：快慢指针，快指针一次走两步，满指针一次走一步。但是细节很重要，比如要找的是中间往前的一个节点

奇数长度找中点，偶数长度找上中点


# 长度小于三的节点
if head is None or head.next is None or head.next.next is None:
		return head
# 长度大于等于三的
fast = head.next.next
slow = head.next
while fast.next and fast.next.next:
		fast = fast.next.next
		slow = slow.next

2. 链表逆序

链表翻转常规有如下两种写法。

更常用原地交换，且谨记：原地交换后 prev为新的头，cur 为空了


# 头插法：将所有节点插入到头节点之前
dummy = Node(0, head)
while head.next:
		temp = head.next
		head.next = head.next.next
		temp.next = dummy.next
		dummy.next = temp
return dummy.next


# 原地交换法
pre = None
cur = head
while cur:
		temp = cur.next
		cur.next= per
		pre = cur
		cur= temp

return pre

3. 多处修改引用

比如提取偶数个链表，将链表按某值按照原有顺序分成三段(小于等于大于)等题目。

套路：假设要分三段，则定义6个变量，分别为三段的起止。分开之后，最后再将其合并起来。


# 给定一列表头节点，和一个特定值。对链表进行分割，使得链表按照
# 小于x的节点、等于x的节点、大于x的节点 排列。每一段链表中节点的顺序需要保持原有的顺序


class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if head is None:
            return head
				# 将链表分三段、所以定义六个变量
        sH, sT = None, None  # 小于段
		    eH, eT = None, None  # 等于段
				bH, bT = None, None  # 大于段

        cur = head
        while cur:
						# 将下一个节点保存下来，且将当前节点和下一个节点断开
            next_ = cur.next
            cur.next = None
						# 分别将当前节点连接到各自的段上
            if cur.val < x:
                if sH is None:
                    sH, sT = cur, cur
                else:
                    sT.next = cur
                    sT =sT.next
            elif cur.val == x:
                if eH is None:
                    eH, eT = cur, cur
                else:
                    eT.next = cur
                    eT = eT.next
						elif cur.val > x:
                if bH is None:
                    bH, bT = cur, cur
                else:
                    bT.next = cur
                    bT = bT.next
            cur = next_
        
				# 将三段连接起来。
				# 注意：连接的时候需要判断是否有空的段
				if sH:
            sT.next = eH
            if eH:
								eT.next = bH
						elif bH:
								sT.next = bH
						return sH
        elif eH:
						eT.next = bH
            return eH
				elif bH:
						return bH

4. 链表相交&环

判断链表中的环，或者判断两链表的相交节点

链表中的环


def detectCycle(self, head: ListNode) -> ListNode:
				# 链表小于三个节点 必定没有环
        if head is None or head.next is None or head.next.next is None:
            return None
				# 链表大于等于三个节点，开始寻找快慢指针相同的节点，
        fast = head.next.next
        slow = head.next

        while fast is not slow:
						# 寻找相同节点的过程中，一旦遇到一个空节点，说明没有环
            if fast.next is None or fast.next.next is None:
                return None
            fast = fast.next.next
            slow = slow.next
				# 找到环中的任意一个节点，让满指针再从头开始找
        slow = head
        while slow is not fast:
            slow = slow.next
            fast = fast.next

      return slow

🥎

142. 环形链表 II

链表的相交

法1：先用hash容器存储一个链表，然后遍历第二个链表，判断每一个节点是否在容器中

法2：考虑到链表相交后便不会再分开了。所以让长链表先走几步，使得俩链表到交点的距离一样。然后同时往前走，直达两相遇

🕹️

160. 相交链表

有环的两链表相交

三种情况：