链表中的双指针

喜欢ヅ旅行 2022-04-24 02:52 227阅读 0赞

学习链表的时候，其添加，删除等操作的复杂度O（1）比较高效，但对其遍历查询复杂度O（n）较高，而且非常不灵活。所以，链表中引入双指针来解决特定问题。  
  
这里说的链表，头结点就是第一个节点，而非伪头结点。  
  
1，环形链表

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

算法：快慢指针指向头结点，块指针走2步，慢指针走1步。如果没有环，快指针将停在链表的末尾。如果有环，快指针最终将与慢指针相遇。（原理：就像跳棋，路径为链表，同时开始，两个棋跳的步数相同时即为相遇）

复杂度分析：时间复杂度O（n）;因为只增加了快慢指针的内存空间，空间复杂度O（1）。

对比于哈希表解决这个问题，空间复杂度O（n）；快慢指针的优势在于内存占用较少。

/**
     * 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) {
        
            if(head == null || head.next == null){
                return false;
            }
            ListNode slow = head;
            ListNode fast = head.next;
            while(slow != fast){
                if(fast == null || fast.next == null){
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
            
        }
    }

2，环形链表II

> 给定一个链表，返回链表开始入环的第一个节点。

算法：（1）先在上题的基础上，找到快慢指针相遇节点（不一定为入环第一个节点）（2）慢指针指向头结点，快慢指针再次相遇即为入环第一个节点。（小编也不知道这是步骤2的设计原因，请大神指教）。

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

3，相交链表

> 找到两个单链表相交的起始节点。

算法：根据相交时，路程相等原理。两个指针分别指向两链表的头结点，同时遍历链表，到达尾节点后指向另一个链表的头结点，直至两结点相等（相交），即为相交的起始结点。

leetcode代码：

public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            /**
            定义两个指针，第一轮让两个到达末尾的节点指向另一个链表的头部，最后如果相遇则为交点
            两个指针等于移动了相同的距离，有交点就返回，无交点就是各走了两条指针的长度
            */
            if(headA == null || headB == null){
                return null;
            }
            ListNode pA = headA,pB = headB;
            // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头，而第二轮体现在如果
            //pA或pB相交就返回交点，不想交最后就是null == null
            while(pA != pB){
                pA = pA == null ? headB : pA.next;
                pB = pB == null ? headA : pB.next;
            }
            return pA;
        }
    }

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

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

算法：前后指针，设定距离为n不变。指针一起移动，等前指针先到达链表尾（Null），此时后指针指向链表的倒数第n个节点的前一个节点，删除其后节点即可。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZWd5MjE4_size_16_color_FFFFFF_t_70]

class Solution {
        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;
            
        }
    }

5，小结 - 链表中的双指针

> leetcode提供了一个模板，用于解决链表中的双指针问题。

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZWd5MjE4_size_16_color_FFFFFF_t_70]: /images/20220221/f9907c0dcb044e4aa83a6abedcdab154.png