双指针技巧，链表

双指针链表

虚拟头节点+双指针，都要用虚拟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);//记录小于xListNode 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;}
}