算法|双指针解决链表

算法 双指针
算法笔记
发布日期:   2022-07-17
更新日期:   2024-01-10
文章字数:   2.2k
阅读时长:   9 分
阅读次数:  

双指针链表题

学习地址：双指针技巧秒杀七道链表题目 :: labuladong的算法小抄

迭代法合并链表

题目：21. 合并两个有序链表 - 力扣（LeetCode）

//迭代法合并有序链表
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //随便来一个头节点
        ListNode p  = new ListNode(-1);
        ListNode q = p;//建立指针
        //比较大小插入链表中
        while(list1 != null && list2 != null){
            if(list1.val > list2.val){
                q.next = list2;
                list2 = list2.next;
                q = q.next;
            }else{
                q.next = list1;
                list1 = list1.next;
                q = q.next;
            }
        }
        //查看最后的是否还剩未分配的。如果有，就放入q中
        q.next = list1 == null ? list2 : list1;
        //返回头节点
        return p.next;
    }
}

迭代法的原理是不断重复

在这里利用迭代法不断比较大小重复操作，直到最后某一个待比较的链表指针指到最后就结束迭代

下边使用动图来演示这个迭代过程

引用labuladong算法小抄的图

与迭代法相对应的，我们还可以使用递归法来解此题，具体可以查看官方题解 合并两个有序链表 - 合并两个有序链表 - 力扣（LeetCode）

利用优先级队列合并K个升序链表

23. 合并K个升序链表 - 力扣（LeetCode）

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //判空一定要有，这是必须要处理的边界条件
        if (lists.length == 0) return null;
        //创建一个头节点
        ListNode p = new ListNode(-1);
        //写一个指针指向的头节点
        ListNode q = p;
        //创建优先级队列，长度就使用表头数量即可，因为下边都是先出后进，可以保证不会超过长度
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.val-b.val));
        //利用优先级队列来载入链表数组（对应的表头）
        for(ListNode listHead : lists){
            if(listHead != null){
                pq.add(listHead);
            }
        }
        //循环载入最小值
        while(!pq.isEmpty()){
            //获取二叉堆中的最小值
            ListNode node = pq.poll();
            //将最小值存入我们预设的链表
            q.next = node;
            //将将被poll出来的value的next值存入二叉堆中
            if(node.next != null){
                pq.add(node.next);
            }
            //指针下移一位
            q = q.next;
        }
        return p.next;
    }
}

这个算法利用了 优先级队列 巧妙的解决了这个问题，下面利用一张图辅助理解。

图中模拟出了链表数组的结构，以及对应的步骤指示

值得一提的是， (a,b)->(a.val-b.val) 这段代码是使用了 lamada 表达式来替代了 Comparator 比较器， 自写Comparator 比较器的功能也是实现类似这样子的一个比较，所以直接使用这段 lamada 表达式就可以替代这段代码了。当然，我们也可以使用对应的自带比较器来实现这个功能

Java集合类学习–PriorityQueue_CodersCoder的博客-CSDN博客

利用双指针+虚拟指针头分隔链表

86. 分隔链表 - 力扣（LeetCode）

题目描述:

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始 相对位置 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode q  = new ListNode(-1);
        ListNode headq = new ListNode(-1);
        ListNode headp = headq;
        headp.next = head;
        ListNode p = q;
        while(headp.next != null){
            if(headp.next.val < x){
                p.next = headp.next;
                headp.next = headp.next.next;
                p = p.next;
                p.next = null;
            }else{
                headp = headp.next;
            }
        }
        p.next = headq.next;
        return q.next;
    }
}

注意双指针的虚拟指针头，并且当把节点分到不同链的时候，要注意链表的合理连通性，去除不合理的连通性。

链表倒数第K个节点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

题目描述

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //设置虚拟头节点，使得唯一的一个值被删掉的时候，该值仍有父节点
        ListNode q = new ListNode(-1);
        q.next = head;
        ListNode p = findFromEnd(q,n+1);
        p.next = p.next.next;
        return q.next;
    }

    private ListNode findFromEnd(ListNode head,int n){
        ListNode p1 = head;
        ListNode p2 = head;

        //L个数据，走到最后一个数据，总步数是L-1，前面先走n-1步
        //留L-n步给p2走
        for(int i = 0; i < n-1; i++){
            p1 = p1.next;
        }

        //一定要做这个next的判空，不然去到空数据处，会使得边界值出错
        //走了L-n步
        while(p1.next != null){
            p1 = p1.next;
            p2 = p2.next;
        }

        return p2;
    }
}

想要一次遍历找到倒数第 k 位的节点，需要让指针在头节点走 n-k+1 位。但是我们事先并不知道 n 是多少，这个时候，可以巧妙的利用双指针来解决这个问题。

  1. 预设在头节点预设 P1 和 P2 两个指针，遍历完链表走到末尾一共会走 L-1 步
  2. 指针 P1 分两阶段走，第一阶段移动的步数为 k-1
  3. 那么剩下的步数就为 L-k 了，这时候开启第二阶段，让 P1 和 P2 一起走，直到 P2 走到尽头。
  4. 这时候，P2 就移动到了第 L-k+1 位，即倒数第 k 位

快慢指针求链表中点

876. 链表的中间结点 - 力扣（LeetCode）

题目描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //下面的判断条件，可以让链表为偶数链的时候，不会出现空指针错误 
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

fast != null && fast.next != null 这段代码可以很好的兼容，不会出现偶数空指针。如果去掉前半部分，只剩下这段判断代码 fast.next != null ，偶数链会出现空指针。下面举个例子：

链为[1,2,3,4,5,6]的链表，当 fast 走到 5 的时候，fast 的下一位是 null 。这时候他再次参与下一轮的判断的时候，它本身就是 null ，所以会出现空指针异常

链表环问题

判断是否环 141. 环形链表 - 力扣（LeetCode）

题目描述:

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            //相遇必有环
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

球形的定理，因为地球是圆的，那么即使路途再远，一直走，终会走到一起

那么不会相遇的，必定不是圆。谁相遇，快慢指针，这个相遇问题也类似行星轨道问题，只不过这里是判断不做计算。

寻找形成环的环起点 142. 环形链表 II - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast,slow;
        fast = slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            //相遇的时候就跳出循环
            if(fast == slow){
                break;
            }
        }
        //如果是由于遍历到最后跳出循环，那么就没有环
        if(fast == null || fast.next == null){
            return null;
        }

        //否则，根据对称原理，继续遍历找出首个成环的点。
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

由于fast 总是比 slow 要多走一杯的距离，所以第一次相遇的时候，当 slow 为 k ，那么 fast 就为 2k 。

由图，多出来的一个 k 恰好是从相遇点环绕了 n 个圈的长度

假设 m 为相遇点距离环起点的距离

那么 k-m 为 head 距离环起点的距离，同时也是在相遇点绕了n圈回到环绕点的距离

所以当指针1从 head 出发，指针2从相遇点出发，他们同时开始以相同速度向前走，最终会以走 k-m 的距离两指针在环起点相遇

相交链表

160. 相交链表 - 力扣（LeetCode）

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1 != p2){
            if(p1 == null){
                p1 = headB;
            }else{
                p1 = p1.next;
            }

            if(p2 == null){
                p2 = headA;
            }else{
                p2 = p2.next;
            }
        }
        return p1;
        
    }
}

文章作者: DYJ
文章链接: https://dyjcow.github.io/2022/07/17/he-bing-you-xu-lian-biao/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 DYJ !
算法 双指针
评论
  目录