湖北建站管理系统信息,合肥网站seo服务,4399游戏官网,提供网站建设的功能力扣labuladong一刷day13天双指针7道链表题
一、21. 合并两个有序链表
题目链接#xff1a;https://leetcode.cn/problems/merge-two-sorted-lists/ 思路#xff1a;合并只需要新new一个虚拟头结点#xff0c;然后遍历比较两个链表把较小的那一个顺序接在虚拟头结点后面。…力扣labuladong一刷day13天双指针7道链表题
一、21. 合并两个有序链表
题目链接https://leetcode.cn/problems/merge-two-sorted-lists/ 思路合并只需要新new一个虚拟头结点然后遍历比较两个链表把较小的那一个顺序接在虚拟头结点后面。遍历停止后把剩余的接上即可。
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode root new ListNode();ListNode p1 list1, p2 list2, p root;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 root.next;}
}二、86. 分隔链表
题目链接https://leetcode.cn/problems/partition-list/ 思路将比x小的节点都放在x的左边其他的保持相对位置那么就相当于把一条链表拆分成两条链表第一条链表都是比x小的第二条链表就是大于等于x的之后再把两条链表拼接在一起即可。
class Solution {public ListNode partition(ListNode head, int x) {ListNode root1 new ListNode();ListNode root2 new ListNode();ListNode p1 root1, p2 root2, p head;while (p ! null) {if (p.val x) {p1.next p;p p.next;p1 p1.next;p1.next null;}else {p2.next p;p p.next;p2 p2.next;p2.next null;}}if (root1.next null) return root2.next;p1.next root2.next;return root1.next;}
}三、23. 合并 K 个升序链表
题目链接https://leetcode.cn/problems/merge-k-sorted-lists/ 思路合并k个升序链表采用优先级队列将所有链表的头结点入队然后遍历返回即可那个节点出队了就把它的next入队即可。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {if (lists.length 0) return null;ListNode root new ListNode();ListNode p root;PriorityQueueListNode queue new PriorityQueue((a, b)- a.val-b.val);for (ListNode list : lists) {if (list ! null) {queue.add(list);}}while (!queue.isEmpty()) {ListNode cur queue.poll();p.next cur;p p.next;if (cur.next ! null) {queue.add(cur.next);}}return root.next;}
}四、19. 删除链表的倒数第 N 个结点
题目链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/ 思路双指针一快一慢相隔n即可。
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode root new ListNode(-1, head);ListNode left root, right root;for (int i 0; i n; i) {right right.next;}while (right.next ! null) {left left.next;right right.next;}left.next left.next.next;return root.next;}
}五、876. 链表的中间结点
题目链接https://leetcode.cn/problems/middle-of-the-linked-list/ 思路求中间节点想一次遍历即可完成只需要采用快慢指针快指针每次比慢指针多走一步快指针抵达终点时慢指针即为中点。
class Solution {public ListNode middleNode(ListNode head) {ListNode slow head, fast head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}return slow;}
}六、141. 环形链表
题目链接https://leetcode.cn/problems/linked-list-cycle/ 思路判断是否成环也是一样的快慢指针只要有环快慢指针就会相遇。
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow head, fast head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) return true;}return false;}
}七、142. 环形链表 II
题目链接https://leetcode.cn/problems/linked-list-cycle-ii/ 思路取巧一点的方式就是用一个hashset把遍历过的节点都放进去只要有重复就有环。
public class Solution {public ListNode detectCycle(ListNode head) {SetListNode set new HashSet();ListNode p head;while (p ! null) {if (set.contains(p)) return p;set.add(p);p p.next;}return null;}
}八、160. 相交链表
题目链接https://leetcode.cn/problems/intersection-of-two-linked-lists/ 思路先算长度长的先走两步等到剩余长度都相等再同步往前走
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA 0, lenB 0;ListNode pa headA, pb headB;while (pa ! null) {lenA;pa pa.next;}while (pb ! null) {lenB;pb pb.next;}pa headA;pb headB;if (lenA lenB) {for (int i lenB; i lenA; i) {pa pa.next;}}if (lenB lenA) {for (int i lenA; i lenB; i) {pb pb.next;}}while (pa ! null pb ! null) {if (pa pb) return pa;pa pa.next;pb pb.next;}return null;}
}
