24. 两两交换链表中的节点

文字讲解：两两交换链表中的节点

视频讲解：帮你把链表细节学清楚！

题设：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

难点：容易出现空指针异常。

思路：奇数偶数分情况，两层判断的逻辑实现。同时每次操作的节点都是交换节点的前一个节点。

ListNode dummy = new ListNode();
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
    ListNode temp = cur.next;
    ListNode temp1 = cur.next.next.next;
    cur.next = cur.next.next;
    cur.next.next = temp;
    cur.next.next.next=temp1;
    cur=cur.next.next;
}
return dummy.next;

易错点：各种next其实不好理解，一定要画图！循环终止条件也是精髓所在。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

19.删除链表的倒数第N个节点

文字讲解：删除链表的倒数第N个节点

视频讲解：链表遍历学清楚！

题设：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

难点：初见比较难有想法。

思路：核心思路为快慢指针移动，先让快指针移动n步，二者再同时移动，当快指针的next指向null时，满指针指向要操作的节点（要操作的节点为删除节点的前一个节点）。当然也可以用移动n+1步解决，终止条件要改一下。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

易错点：理解思路是精髓，本题的循环终止条件并不难。

复杂度分析：

• 时间复杂度: O(n)。
• 空间复杂度: O(1)。

160.链表相交

文字讲解：面试题-链表相交

题设：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

难点：简单题，没有视频讲解也可见一斑，注意细节即可。难点可能在于本题无法Debug。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode curA = headA;
    while (curA != null) {
        ListNode curB = headB;
        while (curB != null) {
            if (curB == curA) {
                return curB;
            }
            curB = curB.next;
        }
        curA = curA.next;
    }
    return null;
}

易错点：然后复杂度就爆炸了，需要进一步简化代码，一次循环搞定。对齐其末尾位置，向前查询。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode curA = headA;
    ListNode curB = headB;
    int lenA = 0, lenB = 0;
    while (curA != null) { // 求链表A的长度
        lenA++;
        curA = curA.next;
    }
    while (curB != null) { // 求链表B的长度
        lenB++;
        curB = curB.next;
    }
    curA = headA;
    curB = headB;
    // 让curA为最长链表的头，lenA为其长度
    if (lenB > lenA) {
        //1. swap (lenA, lenB);
        int tmpLen = lenA;
        lenA = lenB;
        lenB = tmpLen;
        //2. swap (curA, curB);
        ListNode tmpNode = curA;
        curA = curB;
        curB = tmpNode;
    }
    // 求长度差
    int gap = lenA - lenB;
    // 让curA和curB在同一起点上（末尾位置对齐）
    while (gap-- > 0) {
        curA = curA.next;
    }
    // 遍历curA 和 curB，遇到相同则直接返回
    while (curA != null) {
        if (curA == curB) {
            return curA;
        }
        curA = curA.next;
        curB = curB.next;
    }
    return null;
}

复杂度分析：

• 时间复杂度：O(n + m)。
• 空间复杂度：O(1)。

142.环形链表II

文字讲解：环形链表II

视频讲解：把环形链表讲清楚！

题意：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

难点：对于是否包含环的判断，

思路：快慢指针，若其相遇则一定包含环（类似于操场跑步），但是快指针要设为2，每次以一个节点的相对速度靠近慢指针，才不会出现跳过的情况。求出口时本质上为数学题，画图写等式，强烈建议先看一下视频和文字讲解，从零开始的话可能会没啥想法。还有一个核心点是慢指针在进入环中的第一圈一定就会被快指针追上，因为快指针是2，是慢指针的2倍（画图理解）。

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            ListNode index1 = fast;
            ListNode index2 = head;
            while (index1 != index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index1;
        }
    }
    return null;
}

易错点：快指针两步一跳，循环终止条件也要注意。

复杂度分析：

• 时间复杂度: O(n)，快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度。
• 空间复杂度: O(1)。