[超全汇总]数据结构与算法(二)双指针之单链表与数组技巧总结

导读:本篇文章讲解 [超全汇总]数据结构与算法(二)双指针之单链表与数组技巧总结,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

双指针之单链表技巧总结:

1.合并两个有序链表

在这里插入图片描述

这里我们引入其中的双指针加虚拟节点的方法,构建一个新链表,其中p1指针在第一个链表,p2在第二个链表上面,而我们的新链表有个p指针,通过p1.val与p2.val的大小来决定p.next
在这里插入图片描述

//代码实现
class Solution {
    public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(p1 !=null && p2!=null){
            if(p1.val < p2.val){
                p.next = p1;
                p1 = p1.next;
            }else{
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if(p1!=null){
            p.next = p1;
        }
        if(p2!=null){
            p.next = p2;
        }
        return dummy.next;
    }
}

23(hard)合并k个有序链表

这里引入了最小堆,优先队列,这样的好处是我们可以每次poll或者remove都是最小值;

因此当我们构造好一个priorityQueue后,将其list的加进去,就已经构成了一个最小堆

我们每次弹出来的都是最小值

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        //虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        //优先级队列,最小堆
        PriorityQueue<ListNode>pq = new PriorityQueue<>(
            lists.length,(a,b)->(a.val-b.val)
        );
        //将链表的进行排好序
        for(ListNode head:lists){
            if(head !=null){
                pq.add(head);
            }
        }
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            p.next = node;
            if(node.next!=null){
                pq.add(node.next);//让出队列的下一个节点入队列
            }
            p = p.next;
        }
        return dummy.next;
    }
}

寻找链表的任意一处节点

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

在这里插入图片描述

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       ListNode node = findFromend(dummy,n+1);
       node = node.next.next;
       return dummy.next; 
    }

    public ListNode findFromend(ListNode head,int k){
        ListNode p1 = head;
        for(int i = 0;i < k;i++){
            p1 = p1.next;
        }
        ListNode p2 = head;
        while(p1!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}

876.链表的中间节点

在这里插入图片描述

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;
    }
}

160.相交链表

在这里插入图片描述
在这里插入图片描述

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;
    }  
}

双指针中的数组技巧

26.删除有序数组中的重复项

在这里插入图片描述

首先代码在进行原地修改的时候,我们知道是不能产生额外空间的,因此只能采用双指针来进行修改,双指针常用于数组和链表当中

  • 比如一个 0 1 2 2 3 3 4 我们fast,slow都指向初始位置0,如果相等那么fast就往前,遇到不相等的时候停一下,让slow++,将fast的值付给slow
//代码实现
class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length==0) return 0;
        int fast = 0,slow = 0;
        while(fast<nums.length){
            if(nums[fast]!=nums[slow]){
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow+1;
    }
}

83.删除排序链表中重复的元素

在这里插入图片描述

  • 和数组的解法一样,我们对slow 和fast不一样的时候,让slow指向fast,同时slow指针移到fast
//快慢指针
class Solution {
    public ListNode deleteDuplicates(ListNode head) {

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

283、移动零

这里提供两种解法,第一个是通过交换,第二个就是我们前面提说的双指针去掉指定元素

//解法1:通过遇到0就往前走,遇到不是0的时候我们进行交换,这样0就到后面去了
class Solution {
    public void moveZeroes(int[] nums) {
  int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        //使用一个temp来接类似于把大数都往左边移
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    
        }
    }
//解法2:我们将为0的都去掉,返回对应的长度,然后再这个长度往后的都为0
class Solution {
    public void moveZeroes(int[] nums) {
        int p = removeElement(nums,0);
        //将p之后的元素都设置成0
        for(;p<nums.length;p++){
            nums[p] = 0;
        }
    }
    int removeElement(int[]nums,int val){
        int fast = 0,slow = 0;
        while(fast < nums.length){
            if(nums[fast]!=val){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

val){
int fast = 0,slow = 0;
while(fast < nums.length){
if(nums[fast]!=val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/102000.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!