力扣labuladong一刷day13天双指针8道链表题

力扣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;PriorityQueue<ListNode> 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) {Set<ListNode> 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;}
}