力扣labuladong——一刷day14

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

一、力扣21. 合并两个有序链表

/*** 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 head = new ListNode(-1,null);ListNode p1 = list1, p2 = list2, r = head;while(p1 != null && p2 != null){if(p1.val <= p2.val){r.next = p1;p1 = p1.next;r = r.next;}else{r.next = p2;p2 = p2.next;r = r.next;}}if(p1 != null){r.next = p1;}if(p2 != null){r.next = p2;}return head.next;}
}

二、力扣86. 分隔链表

/*** 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 p1 = new ListNode(), p2 = new ListNode();ListNode r1 = p1, r2 = p2, r = head;while(r != null){if(r.val < x){ListNode temp = r;r = r.next;temp.next = null;r1.next = temp;r1 = r1.next;}else{ListNode temp = r;r = r.next;temp.next = null;r2.next = temp;r2 = r2.next;}}r1.next = p2.next;return p1.next;}
}

三、力扣23. 合并 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) {ListNode head = new ListNode(), r = head;if(lists.length == 0){return null;}PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->{return a.val - b.val;});for(ListNode node : lists){if(node != null){pq.add(node);}}while(! pq.isEmpty()){ListNode cur = pq.poll();r.next = cur;cur = cur.next;r = r.next;if(cur != null){pq.add(cur);}}return head.next;}
}

四、力扣19. 删除链表的倒数第 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 res = new ListNode(-1,head);ListNode r1 = res, r2 = res;int len = 0;while(len < n+1){r1 = r1.next;len ++;}while(r1 != null){r1 = r1.next;r2 = r2.next;}r2.next = r2.next.next;return res.next;}
}

五、力扣876. 链表的中间结点

/*** 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 p1 = head, p2 = head;while(p2 != null && p2.next != null){p2 = p2.next;p1 = p1.next;if(p2 != null){p2 = p2.next;}else{break;}}return p1;}
}

六、力扣142. 环形链表 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) {if(head == null)return null;ListNode fast = head, slow = fast;while(fast != null){slow = slow.next;fast = fast.next;if(fast == null){return null;}else{fast = fast.next;if(fast == slow){slow = head;while(slow != fast){slow = slow.next;fast = fast.next;}return fast;}}}return null;}
}

七、力扣160. 相交链表

/*** 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, p2 = headB;ListNode max, min;int lenA = 0, lenB = 0, edge = 0;while(p1 != null){lenA ++;p1 = p1.next;}while(p2 != null){lenB ++;p2 = p2.next;}if(lenA > lenB){edge = lenA - lenB;max = headA;min = headB;}else{edge = lenB - lenA;max = headB;min = headA;}while(edge > 0){edge --;max = max.next;    }while(max != null && min != null){if(max == min){return max;}max = max.next;min = min.next;}return null;}
}