# ===== CodeLab: algo-linkedlist =====
# 以下代码片段按文章出现顺序拼接, 共 6 段

# ----- 片段 1 (python) -----
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(nums):
    """用数组构造链表,返回头节点"""
    dummy = ListNode()      # 哨兵节点,简化边界处理
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

def show(head):
    vals = []
    while head:
        vals.append(str(head.val))
        head = head.next
    print(" -> ".join(vals))

head = build_list([1, 2, 3, 4, 5])
show(head)   # 1 -> 2 -> 3 -> 4 -> 5

# ----- 片段 2 (python) -----
def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next    # 先保存后继
        cur.next = prev   # 指针掉头
        prev = cur        # 前驱前进
        cur = nxt         # 当前前进
    return prev           # 新链表的头

head = build_list([1, 2, 3, 4, 5])
show(reverse_list(head))  # 5 -> 4 -> 3 -> 2 -> 1

# ----- 片段 3 (python) -----
def reverse_rec(head):
    if head is None or head.next is None:
        return head                  # 递归出口:空或只剩一个
    new_head = reverse_rec(head.next)
    head.next.next = head            # 后一个节点指回自己
    head.next = None                 # 断开,防止环
    return new_head

head = build_list([1, 2, 3, 4, 5])
show(reverse_rec(head))  # 5 -> 4 -> 3 -> 2 -> 1

# ----- 片段 4 (python) -----
def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

head = build_list([1, 2, 3, 4, 5])
print(middle_node(head).val)          # 3
head2 = build_list([1, 2, 3, 4, 5, 6])
print(middle_node(head2).val)         # 4(偶数长度取靠后那个)

# ----- 片段 5 (python) -----
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:      # 相遇说明有环
            return True
    return False

# 造一个环:1 -> 2 -> 3 -> 4 -> 2
head = build_list([1, 2, 3, 4])
head.next.next.next.next = head.next
print(has_cycle(head))        # True

# ----- 片段 6 (python) -----
def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p = head
            while p is not slow:   # 同步走,相遇即入口
                p = p.next
                slow = slow.next
            return p
    return None

head = build_list([1, 2, 3, 4])
head.next.next.next.next = head.next
print(detect_cycle(head).val)   # 2