# Leetcode 链表

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

```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

```java
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、找到相交链表

```java
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、反转链表

```java
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的元素【头插法来解决】

```java
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;
}
```

> 头插法关键代码：
>
> ```java
> ListNode next = cur.next;
> cur.next = next.next;
> next.next = pre.next;	// 注意，千万不能写成cur，因为这里cur没有跟着走
> pre.next = next;
> ```

![image-20211005174813148](https://gitee.com/LuckyCurve/img/raw/master//img/image-20211005174813148.png)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luckycurvec.gitbook.io/java-knowledge-architecture/mian-shi-17/leetcode/lian-biao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.