通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode探索之链表学习 双指针技巧

1179人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode

作者:因情语写

链接:https://www.qingyu.blue/article/246

声明:请尊重原作者的劳动,如需转载请注明出处


    我们在另一张卡片中引入了双指针技巧:数据结构简介 - 数组和字符串.

    让我们简要回顾一下这种技巧。 我们提到了两种使用双指针技巧的情景:

  1. 两个指针从不同位置出发:一个从始端开始,另一个从末端开始;
  2. 两个指针以不同速度移动:一个指针快一些,另一个指针慢一些。

    对于单链表,因为我们只能在一个方向上遍历链表,所以第一种情景可能无法工作。然而,第二种情景,也被称为慢指针和快指针技巧,是非常有用的。

    本章节中,我们将重点讨论链表中的慢指针和快指针问题,并告诉你如何解决这类问题。

    链表中的双指针

    让我们从一个经典问题开始:

给定一个链表,判断链表中是否有环。

    你可能已经使用哈希表提出了解决方案。但是,使用双指针技巧有一个更有效的解决方案。在阅读接下来的内容之前,试着自己仔细考虑一下。

    想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。

    这正是我们在链表中使用两个速度不同的指针时会遇到的情况:

  1. 如果没有环,快指针将停在链表的末尾。
  2. 如果有环,快指针最终将与慢指针相遇。

    所以剩下的问题是:

这两个指针的适当速度应该是多少?

    一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

那其他选择呢?它们有用吗?它们会更高效吗?


    算法说明

    环形链表

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

// 想法:暴解:将结点放入List中,看是否会出现相等;或放入Set中,看长度是否增加
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        Set<ListNode> sets = new HashSet<>();
        int length = 1;
        while(head != null){
            sets.add(head);
            if(sets.size() != length++){
                return true;
            }
            
            head = head.next;
        }
        
        return false;
    }

    通过将结点放入set中,如果放入后长度不增加说明有环,但不是常量内存,看一下其它的解法

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null ){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }

    使用了快慢指针,如果存在环的话,可以证明快慢指针一定会相遇,如下图,当慢指针进入环时,快指针已经在环中一个位置(7),快指针的位置还有几个元素到环入口(此时慢指针在环入口),只要走相隔的元素的步数,快慢指针就会相遇,如下图快指针再有两个元素(8,1)到环入口,那么再循环两次(走两次),那么快慢指针将在3处相遇

    环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

进阶:
你是否可以不用额外空间解决此题?

// 想法:用Set,add后长度不增加则重复了,说明是入口
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        
        Set<ListNode> set = new HashSet<ListNode>();
        int len = 0;
        while(head != null){
            set.add(head);
            if(set.size() != ++len){
                return head;
            }
            
            head = head.next;
        }
        
        return null;
    }

    还是用set,如果长度不增加,说明出现重复了,这个重复的就是环的入口,这里用了o(n)的辅助空间,看一种更好的解法

public ListNode detectCycle(ListNode head) {
        if (head == null)
            return head;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    这里没有使用额外的空间,这里当第一次相遇时,使慢指针返回head,再次相遇时即是在环入口相遇,这里解释一下,如下图,设当第一次相遇时慢指针走了a个元素,快指针走了b个元素,此时b=2a(因为慢指针走一步快指针走两步),即2(M+N)=M+N+L+N,即L=M,此后慢指针回到head,快指针变得和慢指针同速,当慢指针走M到环入回时,快指针也走了M(即L)也到了环入口,即会在环入口再次相遇。

    相交链表

编写一个程序,找到两个单链表相交的起始节点。

    如下面的两个链表

在节点 c1 开始相交。

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
// 想法:这次用List
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        List<ListNode> listA = new ArrayList<>();
        List<ListNode> listB = new ArrayList<>();
        
        while(headA != null) {
        	listA.add(headA);
        	headA = headA.next;
        }
        
        while(headB != null) {
        	listB.add(headB);
        	headB = headB.next;
        }
        
        ListNode result = null;
        
        for(int i = listA.size() - 1; i >= 0; i--) {
        	if(listB.contains(listA.get(i))) {
        		result = listA.get(i);
        	}else {
        		break;
        	}
        }
        
        return result;
    }

     因为没有环,所以我用了list存储两个相交的链表,并找出其中第一个共同的结点,看一下更好的方法

/**
 * 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) {
        int size1 = 0;
        int size2 = 0;
        ListNode pointer = headA;
        while (pointer != null) {
            size1++;
            pointer = pointer.next;
        }
        pointer = headB;
        while (pointer != null) {
            size2++;
            pointer = pointer.next;
        }

        int size = Math.abs(size1 - size2);
        if (size1 > size2) {
            for (int i = 0; i < size; i++) {
                headA = headA.next;
            }
        } else {
            for (int i = 0; i < size; i++) {
                headB = headB.next;
            }
        }
        
        while (headA !=null && headB !=null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

    这里的想法是找到较长链表的后若干个元素,这里的后若干个元素指较短链表长度个元素,这样不相交部分的长度就相同了,此时两个链表每次向后移动一个位置,会同时到达相交的位置

    删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

// 想法:先求出链表长度,然后用倒数算出正数(length - n + 1)
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        ListNode temp = head;
        while(temp != null){
            length++;
            temp = temp.next;
        }
        
        int target = length - n + 1;
        if(target == 1){
            head = head.next;
            return head;
        }
        
        ListNode pre = head;
        temp = head.next;
        int cur = 2;
        
        
        while(target != cur){
            pre = temp;
            temp = temp.next;
            cur++;
        }
        
        pre.next = temp.next;
        
        return head;
    }

     第一趟先求出链表长度,第二趟找到要求位置元素并删除,但用了两趟循环,下面看一种更好的算法

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        
        for(int i=1;i<=n+1;i++)
        {
            first = first.next;
        }
        while(first!= null)
        {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    用了两个指针,第一个指针先走到第n个元素后,然后两个指针再一起走,当第一个指针走完链表(走了链表长度)时,第二个指针走了链表长度减n+1个元素,走到了倒数第n个元素前,此时使second.next = second.next.next;即可,循环了两次,但两次循环的总长度是链表的长度


    小结 - 链表中的双指针

    在这里,我们为你提供了一个模板,用于解决链表中的双指针问题。

// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem

    提示

    它与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点:

    1. 在调用 next 字段之前,始终检查节点是否为空。

    获取空节点的下一个节点将导致空指针错误。例如,在我们运行 fast = fast.next.next 之前,需要检查 fast 和 fast.next 不为空。

    2. 仔细定义循环的结束条件。

    运行几个示例,以确保你的结束条件不会导致无限循环。在定义结束条件时,你必须考虑我们的第一点提示。

    复杂度分析

    空间复杂度分析容易。如果只使用指针,而不使用任何其他额外的空间,那么空间复杂度将是 O(1)。但是,时间复杂度的分析比较困难。为了得到答案,我们需要分析运行循环的次数。

    在前面的查找循环示例中,假设我们每次移动较快的指针 2 步,每次移动较慢的指针 1 步。

  1. 如果没有循环,快指针需要 N/2 次才能到达链表的末尾,其中 N 是链表的长度。
  2. 如果存在循环,则快指针需要 M 次才能赶上慢指针,其中 M 是列表中循环的长度。

    显然,M <= N 。所以我们将循环运行 N 次。对于每次循环,我们只需要常量级的时间。因此,该算法的时间复杂度总共为 O(N)。

    自己分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析,请考虑最糟糕的情况。


自己写的文章声明标题示例:


点赞(0) 打赏

全部评论

还没有评论!