算法题--快慢指针

### 快慢指针

快慢指针用于解决那些寻找指定链表指定节点或删除链表指定节点的问题。通常在不知道链表长度情况下只需要遍历一遍链表即可。

核心思想是使用两个指针，一个走的比较快，一个走的比较慢；快的走到链表尾部时，慢的所在位置正是我们要找的节点。

常用的方法是两指针间隔指定长度，和两指针按照特定步长前进。

> 参考：https://zhuanlan.zhihu.com/p/76011453

### 题目1：

删除倒数第n个元素：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 要求： 只允许对链表进行一次遍历。

#### 思路：

要删除倒数第n个元素，首先我们应该这样想：如果使用一个指针遍历链表，当我走到倒数第n个元素时，我想要删除他，但是由于不知道链表长度（只能遍历一遍链表，注定我们无法获取链表长度），我们就不知道我们现在遍历到倒数第n个元素了，所以如果有另一个指针在前面给我们接应就好了。那另一个指针怎么知道我们遍历到倒数第n个元素了，怎么知道要何时通知我们呢？

![](http://minio.riun.xyz/riun1/2022-02-25_2aC3CfoVnERdPzs7wj.jpg)

假设我们要删除倒数第3个元素，第一个指针是p1，当p1走到对应位置时，p2走到某个位置，他感觉到该提醒我们了，这个位置该是什么呢？就是null！因为链表上所有位置都是一样的，都是非null的节点，所以只要在链表上，p2指针就不知道自己在哪，不知道自己该不该提醒p1；只有p2走到null时，它才会知道自己遍历的节点发生了改变：由非null，变为了null。

所以p1在指定节点时，p2应该在null，也就是走到了最后。观察一下，p1与p2此时距离刚好是n（不是间隔3个元素，而是索引值相减是3）。所以我们需要让p1与p2相差指定的间隔n，然后同步向前走，这样当p2走到null时，p1就是要删除的元素！。

这里可以做个小优化，我们是要删除元素的，所以我们最后想要拿到的是被删除元素的前一个节点，也就是被删除元素的前驱节点。将前驱结点的next指向前驱节点的后置的后置节点。这样就不用额外的变量记录p1的pre了。

#### 代码：

```java
package com.example.demo.core.Leecode;

/**
 * @author: HanXu
 * on 2022/2/25
 * Class description: 链表系列算法
 */
public class LinkedDemo {
    //链表节点
    static class Node {
        int val;
        Node next;

public Node() {
        }

public Node(int val) {
            this.val = val;
        }
    }

public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        Node node = buildLinked(arr);
        printLinked(node);

Node node1 = removeDnNode(node, 2);
        printLinked(node1);
        /*
        1 2 3 4 5 
		1 2 3 5 
        */
    }

/**
     * 删除倒数第n个元素
     * 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 要求： 只允许对链表进行一次遍历。
     * @param head 头结点（头结点不存值）
     * @param n n值保证有效
     * @return 头结点
     */
    public static Node removeDnNode(Node head, int n) {
        //fast和slow相距n个元素，例如n是1时，那么slow是head，fast就是第一个节点。n是二时，slow是head，fast就是第二个节点。
        Node fast = head.next;
        for (int i = 1; i < n; i++) {
            fast = fast.next;
        }

Node slow = head;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        //当前节点就是要删除的节点的前驱结点，将前驱节点的next指向它自己的下下一个节点，就把要删除的元素删除了。
        slow.next = slow.next.next;
        return head;
    }

/**
     * 打印链表
     * @param node
     */
    public static void printLinked(Node node) {
        while (node.next != null) {
            node = node.next;
            System.out.print(node.val + " ");
        }
        System.out.println();
    }

/**
     * 构建链表
     * @param arr
     * @return 返回头节点
     */
    public static Node buildLinked(int[] arr) {
        Node head = new Node();
        Node pNode = head;
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            pNode.next = node;
            pNode = node;
        }
        return head;
    }
}
```

### 题目2：

给定一个头结点为 `head` 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

来源：[力扣（LeetCode）](https://leetcode-cn.com/problems/middle-of-the-linked-list)

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

来源：[力扣（LeetCode）](https://leetcode-cn.com/problems/middle-of-the-linked-list)

#### 思路：

快慢指针常用的就两个思路：一个是两个指针指定间隔；另一个就是两个指针按照某种特定步长。这个题目就是需要按照特定步长走。思考一下，一个指针走到中间，另一个指针已经走到了结尾（另一个指针必须要走到结尾，前面我们说过的，不然不知道何时提醒），这是什么？2倍啊，没错，快指针的步长是慢指针的2倍。慢指针每次走1步，快指针每次走2步即可。

#### 代码：

```java
package com.example.demo.core.Leecode;

/**
 * @author: HanXu
 * on 2022/2/24
 * Class description: 链表的中间节点
 */
public class LinkedDemo {

static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        ListNode head = buildLinked(arr);
        printLinked(head);
        ListNode node = middleNode(head);
        printLinked(node);
        /*
        1 2 3 4 5 
        3 4 5 
        */
    }

/**
     * 给定一个头结点为 `head` 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
     * 1 2 3 4 5 中间节点是3 返回ListNode(val = 3, next = 4)
     * 1 2 3 4 中间节点是2,3 返回ListNode(val = 3, next = 4)
     * 1 2 3 4 5 6
     * @param head
     */
    public static ListNode middleNode(ListNode head) {
        //这两行代码是因为提交LeeCode时，发现LeeCode的head是第一个元素，而不是头结点。所以为了不改变后面的代码，我就自己在函数内部造了一个头结点。
        ListNode headHead = new ListNode();
        headHead.next = head;

ListNode slow = headHead, fast = headHead;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //观察可以发现，奇数长度时，出循环的时候fast是null（这个时候slow刚好是中间那个）；偶数长度时，出循环时fast不是null，fast.next是null(这个时候slow是中间两个左边那个)
        if (fast == null) {
            return slow;
        } else {
            return slow.next;
        }
    }

/**
     * 打印链表
     * @param head
     */
    private static void printLinked(ListNode head) {
        ListNode pNode = head;
        while (pNode != null) {
            System.out.print(pNode.val + " ");
            pNode = pNode.next;
        }
        System.out.println();
    }

/**
     * 构建链表
     * @param arr
     * @return 返回的是第一个元素，而不是head
     */
    private static ListNode buildLinked(int[] arr) {
        ListNode head = new ListNode();
        ListNode pNode = head;
        for (int i = 0; i < arr.length; i++) {
            ListNode listNode = new ListNode(arr[i]);
            pNode.next = listNode;
            pNode = pNode.next;
        }
        return head.next;
    }
}
```

算法题--快慢指针

文章目录

发表评论