labuladong刷题——第一章（1） 双指针技巧秒杀七道链表题目

双指针技巧秒杀七道链表题目

---

1.合并两个有序链表 LeetCode21

输入两个链表，合并成一个新的有序链表。很简单，注意头结点的使用即可。

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        /*
        关键在于这个头指针dummy，他创造了一个空指针指向堆头
        */
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;
    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        // 实际上这个链表是由p指针完成的.
        p = p.next;
    }
    if (p1 != null) p.next = p1;
    if (p2 != null) p.next = p2;
    return dummy.next;
}

---

2.单链表的分解 LC86

在合并两个有序链表时让你合二为一，而这里需要分解让你把原链表一分为二。具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起，就得到了题目想要的结果。

class Solution {
    public ListNode partition(ListNode head, int x) {
    /*
    还是注意头结点的应用,这里用了两个dummy
    p负责遍历原来的链表 p1和p2用来生成结果链表
    如果val小于x,用p1指向它,如果val大于x就用p2指向它
    创建两个新的链表,最后将他们连在一起即可
    */
        ListNode dummy1 = new ListNode(-1);
        ListNode dummy2 = new ListNode(-1);
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;
        ListNode p = head;
        while (p != null) {
            if (p.val < x) {
                p1.next = p;
                p1 = p1.next;
            } else {
                p2.next = p;
                p2 = p2.next;
            }
            /**
             * 这一段是为了让原来的链表断开
             * 保证每一次p都指向一个单独的,只有后继结点的链表
             * 为了断开原有的指针
             * 比如p1指向第一个结点 p2指向第二个节点 如果没有断开
             * 那么p1就会同时指向第三个节点和第二个节点,会出错
             * 当然也可以创建新的链表
             */
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }
        p1.next = dummy2.next;
        return dummy1.next;
    }
}

---

3.合并 k 个有序链表 LC23

 这里要用到PriorityQueue这个数据结构。

PriorityQueue（优先队列） 采用的是堆排序，
实际上是一个堆（不指定Comparator时默认为最小堆）
队列既可以根据元素的自然顺序来排序，也可以根据 Comparator来设置排序规则。

由于是一个队列，操作的时候可以用offer()、poll()、remove() 、add() 方法。offer和add都是添加元素，remove和poll都是删除元素。peek方法是找到头元素但是不删除。

可以自己指定排序方法：

PriorityQueue queue = new PriorityQueue(
        10, //容量
        new Comparator(){
            public int compare(Integer a, Integer b){
                return a-b; //if a>b 则交换，so这是递增序列
            }
    });

总体思路：将每个队列的头结点（因为已经排好序）放到小顶堆中，然后每次从其中取出一个来加入新的链表，之后将拿出来的这个节点的next加入到小顶堆中即可。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        /**
         * 注意最小堆PriorityQueue的用法
         * 就是把链表的头结点塞进去
         */
        if(lists.length==0) return null;
 
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
 
        // lambda表达式，表示构造函数的时候按照从小到大排列
        // 如果a.val-b.val>0 那么a就在b的前面
        PriorityQueue pq = new PriorityQueue<>(lists.length,
                new Comparator(){ //比较器比较的是ListNode
                    public int compare(ListNode a,ListNode b){
                    return a.val-b.val;
                    //if a>b 则交换，so这是小顶堆
            }
        });
        for (ListNode head:lists){
            if(head!=null){
                pq.add(head);
            }
            //注意 这里加入的只是头结点
            //为什么捏?看后面
        }
 
        //开始从pq里面取值
 
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            p.next = node;
            if(node.next!=null){
                pq.add(node.next);
            }
            p = p.next;
        }
        return dummy.next;
    }
}

---

4.两个链表是否相交

其实很简单，从a1开始和从b2开始，两个点走完全长以后从另一个结点开始就可以了。

 

 
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * 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 dummy1 = headA;
        ListNode dummy2 = headB;
        while(headA!=headB){
            if(headA==null) headA = dummy2;
            else headA = headA.next;
            if(headB==null) headB = dummy1;
            else headB = headB.next;
        }
        return headA;
    }
}
//leetcode submit region end(Prohibit modification and deletion)