双指针技巧，链表

双指针链表

虚拟头节点+双指针，都要用虚拟1头节点

合并两个有序链表

设置双指针，都指向虚拟头节点

ListNode list1 代表的是头节点

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy=new ListNode(-1);
        ListNode p=dummy;
        ListNode p1=list1;
        ListNode p2=list2;
        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;
    }
}

单链表的分解（两个小链表可能会成环，要处理

具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 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 dummy1=new ListNode(-1);//记录小于x
        ListNode dummy2=new ListNode(-1);
        ListNode p=head,p1=dummy1,p2=dummy2;
        while(p!=null){
            if(p.val<x){
                p1.next=p;
                p1=p1.next;
            }else{
                p2.next=p;
                p2=p2.next;
            }
            ListNode temp=p.next;//断开p的next，否则会成环
            p.next=null;
            p=temp;
            
        }
        p1.next=dummy2.next;
        return dummy1.next;
    }
}

合并k个升序链表（用优先队列实现最小堆

每次弹出最小的结点值，给新链表。

弹出一个，要再存入一个

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy=new ListNode(-1);
        ListNode p=dummy;
        PriorityQueue<ListNode> pq=new PriorityQueue<>((a,b)->(a.val-b.val));//创建最小堆
        for(ListNode head:lists){
            if(head!=null) pq.add(head);
        }
        while(!pq.isEmpty()){
            ListNode node=pq.poll();//弹出一个最小的
            if(node.next!=null){
                pq.add(node.next);//存入下一个结点
            }
            p.next=node;
            p=p.next;
        }
        return dummy.next;
    }
}

删除链表倒数第n个结点

定义两个指针，一个在左一个在右边，距离为n，右指针走n次即可。走到最后一个结点则停止，因为删除结点要知道要删除结点的前一个结点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy=new ListNode(-1,head);
        ListNode left=dummy;
        ListNode right=dummy;
        while(n-->0){
            right=right.next;
        }
        while(right.next!=null){
            left=left.next;
            right=right.next;
        }
        left.next=left.next.next;
        return dummy.next;
    }
}

链表的中间结点

定义快慢指针，走两步和走一步。返回slow.next

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode dummy=new ListNode(-1,head);
        ListNode slow=dummy,fast=dummy;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow.next;
    }
}

环形链表

快慢指针判断链表是否为环形，在相遇点时，slow重置到head。快慢指针同时开始走1步直到相遇则是环。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;//这里条件是或
        ListNode slow=head;
        ListNode fast=head;
        ListNode p=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast) break;
        }
        if(slow!=fast){
            return null;
        }
        slow=head;
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}

相交链表

遍历完A遍历B，遍历完B遍历A，之后会相交

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1=headA;
        ListNode p2=headB;
        while(p1!=p2){
            p1=p1.next;
            p2=p2.next;
            if(p1==null&&p2==null) return null;
            if(p1==null) p1=headB;
            if(p2==null) p2=headA;
        }
        return p1;
    }
}