两两交换链表中的节点

为了简化操作，我们可以通过引入一个虚拟头节点来处理。以下是两种实现方法：

迭代法

通过使用临时变量保存相关节点的引用，逐步完成节点交换。

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;

    while (prev.next != null && prev.next.next != null) {
        ListNode first = prev.next;
        ListNode second = prev.next.next;

        // 交换逻辑
        first.next = second.next;
        second.next = first;
        prev.next = second;

        // 移动指针
        prev = first;
    }
    return dummy.next;
}

递归法

利用递归从链表末尾开始逐层返回并进行节点交换。

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode nextNode = head.next;
    head.next = swapPairs(nextNode.next);
    nextNode.next = head;

    return nextNode;
}

删除链表倒数第N个节点

双指针技巧是解决该问题的关键。定义两个指针，让快指针先移动N步，然后同时移动快慢指针直到快指针到达末尾。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n + 1; i++) {
        fast = fast.next;
    }

    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;
    return dummy.next;
}

链表相交检测

判断两条链表是否相交，并找到相交点。

方法一：长度对齐法

计算两条链表的长度差，让较长的链表先走几步，之后同步遍历寻找相交点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;

    int lenA = getLength(headA), lenB = getLength(headB);
    ListNode curA = headA, curB = headB;

    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            curA = curA.next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            curB = curB.next;
        }
    }

    while (curA != curB) {
        curA = curA == null ? null : curA.next;
        curB = curB == null ? null : curB.next;
    }
    return curA;
}

private int getLength(ListNode node) {
    int length = 0;
    while (node != null) {
        length++;
        node = node.next;
    }
    return length;
}

方法二：双指针交替遍历法

分别从两条链表头部开始遍历，当一条链表遍历完后切换到另一条链表继续遍历，最终会在相交点相遇。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode p1 = headA, p2 = headB;

    while (p1 != p2) {
        p1 = p1 == null ? headB : p1.next;
        p2 = p2 == null ? headA : p2.next;
    }
    return p1;
}

环形链表入口检测

首先用快慢指针判断是否存在环，然后通过特定算法找到环的入口。

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    boolean hasCycle = false;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }

    if (!hasCycle) return null;

    ListNode ptr1 = head, ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
    }
    return ptr1;
}