合并两个有序链表
**
* 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 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 = p2;
p2 = p2.next;
}else{
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
//运行到此处，循环结束，剩余的一个链表部分，直接挂在新链表尾部
if(p1 != null){
p.next = p1;
}
if(p2 != null){
p.next = p2;
}
//从虚拟头结点之后开始算新的链表
return dummy.next;
}
}
合并k个升序链表
/**
* 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 mergeKLists(ListNode[] lists) {
if(lists.length == 0) return null;
//虚拟头结点
ListNode dummy = new ListNode();
ListNode p = dummy;
//创建一个优先级队列
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b) -> (a.val - b.val));
//将k个结点存储到队列中
for(ListNode head : lists){
if(head != null){
pq.add(head);
}
}
//队列不为空的时候，将队列的数据取出，塞到新队列后面之后，将下一个非空结点塞到新的链表中
while(!pq.isEmpty()){
ListNode minNode = pq.poll();
p.next = minNode;
if(minNode.next != null){
pq.add(minNode.next);
}
p = p.next;
}
return dummy.next;
}
}
链表的中间结点
/**
* 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 middleNode(ListNode head) {
ListNode slow,fast;
slow = fast = head;
//慢指针一次跳1步，快指针，一次跳2步。等快指针走到边界的时候，慢指针刚好走到中点
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
环形链表（简单）
/**
* 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) {
ListNode slow ,fast;
slow = fast = head;
//快慢指针，快慢指针相交，即为有环
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
环形链表II
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow ,fast;
slow = fast = head;
//快慢指针，快慢指针相交，即为有环
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
break;
}
}
if(fast == null || fast.next == null){
return null;
}
slow = head;
while(slow!=fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
删除链表倒数第N 个节点
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
//删除倒数第k个结点，需要找到倒数第k+1个结点，然后将这个结点的next指向next的next结点。
ListNode end = findFromEnd(dummy, n + 1);
end.next = end.next.next;
return dummy.next;
}
public ListNode findFromEnd(ListNode head, int k){
//双指针，先让p1指针走k步
ListNode p1 = head;
for(int i = 0; i< k; i++){
p1 = p1.next;
}
ListNode p2 = head;
//p1,p2指针同时走，先走的p1,需要走n-k步，到链表尾部，p2走n-k步，刚好到倒数第k个结点。
while(p1 != null){
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
}
相交链表
/**
* 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 p1 = headA;
ListNode p2 = headB;
//两个指针分别从A ，B 开始循环遍历，遍历结束开始遍历另外一张链表，两个指针相等时退出。
while(p1 != p2){
if(p1==null){
p1 = headB;
}else{
p1 = p1.next;
}
if(p2 == null){
p2 = headA;
}else{
p2 = p2.next;
}
}
return p1;
}
}
