链表结点定义

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

1. 反转链表（头插法）

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        newHead = None
        cur = head
        while cur:
            curNext = cur.next
            cur.next = newHead
            newHead = cur
            cur = curNext
        return newHead

2. 链表的中间结点（快慢指针）

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

3. 回文链表（中间结点+反转链表）

Python特性法：存入数组直接逆置判断

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        val = []
        while head:
            val.append(head.val)
            head = head.next
        return val == val[::-1]

传统思路：中间结点+反转链表+判断

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if head is None: return True
        fast = slow = head
        # [1] slow 找到中间结点
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next

        # [2] 反转后半段，以newHead为头结点
        newHead = None
        cur = slow.next
        slow.next = None
        while cur:
            curNext = cur.next
            cur.next = newHead
            newHead = cur
            cur = curNext

        # [3] 判断
        while newHead:
            if head.val != newHead.val:
                return False
            head = head.next
            newHead = newHead.next
        return True

4. 合并两个有序链表

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        newHead = ListNode(-1)
        cur = newHead
        while list1 and list2:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        if list1:
            cur.next = list1
        else:
            cur.next = list2
        return newHead.next

5. 相交链表

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if headA == None or headB == None: return None
        nodeA = headA
        nodeB = headB
        while nodeA != nodeB:
            if nodeA != None:
                nodeA = nodeA.next
            else:
                nodeA = headB

            if nodeB != None:
                nodeB = nodeB.next
            else:
                nodeB = headA
        return nodeA

6. 环形链表

快慢指针判断

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None or head.next is None: return False
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            # 注意先走完再判断！
            if fast == slow:
                return True
        return False

用 set() 集合存储所有可能性

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False