算法通关村第一关——链表经典问题之双指针专题笔记

柔光的暖阳◎ 2024-03-22 21:02 70阅读 0赞

### 寻找中间节点 ###

#### 题目描述 ####

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

#### 示例 ####

>     * 示例1：
>     * 输入：【1,2,3,4,5】
>     * 输出：3
>     * 示例2：
>     * 输入：【1,2,3,4,5,6】
>     * 输出：4

#### 解题思路 ####

> 使用快慢指针能够迅速地找到中间节点。当fast指针叨叨链表尾部时，slow一定指向中间元素
> 
> 要点：因为链表顺序是从1开始的 ，所以会返回中间的元素【即如果单链表的节点个数是单数，返回中间的那个元素；如果单链表的节点个数是双数，则返回中间靠后的元素】；但如果是数组则会返回前一个元素，因为数组的下标是从0开始的

#### 代码实现 ####

/**
         * 给定一个头节点为head的非空单链表，返回链表的中间节点；如果中间有两个节点（节点个数为双数），则返回第二个节点
         * 示例1：
         * 输入：【1,2,3,4,5】
         * 输出：3
         * 示例2：
         * 输入：【1,2,3,4,5,6】
         * 输出：4
         * 思路1：使用快慢指针实现：当fast达到链表尾部时，slow一定指向中间
         * @param head 非空的头节点
         * @return 中间节点
         */
        public DoubleNode findMiddleNode(DoubleNode head){
            DoubleNode fast = head , slow = head;
            while (fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

### 寻找倒数第K的元素 ###

#### 题目描述 ####

> 输入一个链表，输出该链表中的倒数第K个节点。本题是从1开始计数，即链表的尾节点是倒数第一个节点

#### 示例 ####

> 给定一个链表： 1 -> 2 -> 3 -> 4 -> 5 ，和k=2
> 
> 返回链表： 4 ->5

#### 解题思路 ####

> ①使用快慢双指针：先将fast向后遍历到第k+1个节点，slow仍然指向链表的第一个节点，此时指针fast与slow两者之间刚好间隔k个节点。之后两个指针同步向后走，当fast走到链表的尾部空节点时，slow指针刚好指向链表的倒数第k个节点
> 
> ②使用栈实现：由于栈的特点是先进后出，因此栈出栈刚好就像倒序遍历链表一样。

#### 代码实现 ####

注意点：链表的长度有可能小于k，寻找k位置的时候必须判断fast是否为null，不然会爆空指针异常。

/**
         * 题目描述：输入一个链表，输出该链表中的倒数第K个节点。本题是从1开始计数，即链表的尾节点是倒数第一个节点
         * 示例:
         * 给定一个链表： 1 -> 2 -> 3 -> 4 -> 5 ，和k=2
         * 返回链表： 4 ->5
         *
         * 思路：①使用快慢双指针：先将fast向后遍历到第k+1个节点，slow仍然指向链表的第一个节点，此时指针fast与slow两者之间刚好间隔k个节点。
         * 之后两个指针同步向后走，当fast走到链表的尾部空节点时，slow指针刚好指向链表的倒数第k个节点
         * ②使用栈实现：由于栈的特点是先进后出，因此栈出栈刚好就像倒序遍历链表一样。
         * @param head 链表
         * @param k 倒数第k个元素
         * @return 倒数第k个元素的位置
         */
        public DoubleNode getKthFromEnd(DoubleNode head,int k){
            DoubleNode fast = head , slow = head;
            // 由题可知，从1 开始计数
            int count = 1;
            while (count < k + 1 && fast!=null){
                fast = fast.next;
                count++;
            }
            while (fast != null){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }

### 旋转链表 ###

#### 题目描述 ####

> 给定一个链表的头节点head，旋转链表，将链表每个节点向右移动k个位置

#### 示例 ####

> 输入：head = \[1,2,3,4,5\] , k=2
> 
> 输出：\[4,5,1,2,3\]

#### 图示 ####

![18a1faa8dab14ba09e2ce629cf6ba4d9.png][]

#### 解题思路 ####

> 思路1：将整个链表反转变成\{5,4,3,2,1\}，然后将前K和N-K两个部分分辨饭庄，也就是分别变成了\{4,5\}和\{1,2,3\}，这样就轻松解决了

> 思路2： 先用双指针策略找到倒数K 的位置，也就是\{1,2,3\}和\{4,5\}两个序列，之后再将两个链表拼接成\{4,5,1,2,3\}就行

思路2 具体过程

> 因为k有可能大于链表长度，所以首先获取一下链表长度len，然后k = k % len；如果k == 0，表示不用旋转，直接返回头节点。否则：
> 
> 快指针先走k步
> 
> 慢指针和快指针一起走
> 
> 快指针走到链表尾部时，慢指针所在位置刚好是要断开的地方，把快指针指向的节点连到原链表头部，慢指针指向的节点断开和下一个节点的联系
> 
> 返回结果时，慢指针指向节点的下一个节点

#### 代码实现 ####

/**
         * 给定一个链表的头节点head，旋转链表，将链表每个节点向右移动k个位置
         * 示例：
         * 输入：head = [1,2,3,4,5]，k=2
         *
         * 输出：[4,5,1,2,3]
         *
         * @param head 链表头节点
         * @param k 右移k个位置
         * @return 旋转链表后的头节点
         */
        public DoubleNode rotateNode(DoubleNode head , int k){
            //如果k == 0，表示不用旋转，直接返回头节点
            if (head == null || k==0){
                return head;
            }
            // 定义快慢指针和临时变量
            DoubleNode fast = head;
            DoubleNode slow = head;
            DoubleNode temp = head;
            int len = 0;
    
            // 获取链表的长度
            while (head!=null){
                head = head.next;
                len++;
            }
            //k = k % len；如果k == 0，表示不用旋转，直接返回头节点
            if (k % len == 0){
                return head;
            }
            // 如果k > 0，表示要旋转，并且右移k次
            while (k % len >0){
                k--;
                fast = fast.next;
            }
            // 这时候 fast指针走了k步，slow指针和fast同时移动
            while (fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
    
            DoubleNode res = slow.next;
            slow.next = null;
            fast.next = temp;
            return res;
        }

[18a1faa8dab14ba09e2ce629cf6ba4d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/0c1babc53d40405cb2ca3b43432fc45d.png