Leetcode 链表

链表当中有相当一部分题目需要使用双指针的方式来进行解决，双指针标准Java代码：

ListNode fast = head, slow = head;

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

// TODO

1、获取倒数第K个元素：快慢指针，fast先走K步，然后返回slow指针即可

2、获取中间位置的元素：快慢指针，返回slow

3、判断是否有环：快慢指针，先走，碰撞了之后返回true

4、寻找环入口，如果不存在就返回null

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

    while (true) {
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;

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

    fast = head;

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

    return fast;
}

5、找到相交链表

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

    return curA;
}

反转链表类，都只需要在外部定义pre和cur即可

6、反转链表

public ListNode reverseList(ListNode head) {
    ListNode pre = null, cur = head;

    while (cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;

        pre = cur;
        cur = temp;
    }

    return pre;
}

7、反转链表Ⅱ：反转left到right的元素【头插法来解决】

public ListNode reverseBetween(ListNode head, int left, int right) {
    // 防止left为1，使用虚拟头结点来解决
    ListNode virtualNode = new ListNode();

    virtualNode.next = head;

    ListNode pre = virtualNode, cur;
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }

    cur = pre.next;

    for (int i = left; i < right; i++) {
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }

    return virtualNode.next;
}

头插法关键代码：

ListNode next = cur.next;
cur.next = next.next;
next.next = pre.next;	// 注意，千万不能写成cur，因为这里cur没有跟着走
pre.next = next;

image-20211005174813148