1669. 合并两个链表

一时失言乱红尘 2023-10-05 21:25 24阅读 0赞

给你两个链表 `list1` 和 `list2` ，它们包含的元素分别为 `n` 个和 `m` 个。

请你将 `list1` 中第 `a` 个节点到第 `b` 个节点删除，并将`list2` 接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：

![c8af70495edc801909cd31d8772ddba1.png][]

请你返回结果链表的头指针。

**示例 1：**

![ee2696d40c6a78d51730772dbfc52657.png][]

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
    输出：[0,1,2,1000000,1000001,1000002,5]
    解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

**示例 2：**

![f22bc506d9ae224be539ec6f98b19c06.png][]

输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
    输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
    解释：上图中蓝色的边和节点为答案链表。

**提示：**

*  `3 <= list1.length <= 104`
 *  `1 <= a <= b < list1.length - 1`
 *  `1 <= list2.length <= 104`

package Solution1669;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    import java.util.Stack;
    
    class Solution {
    	public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
    		ListNode dummy1 = new ListNode(-1);
    		ListNode s = dummy1;
    
    		ListNode dummy2 = new ListNode(-1);
    		ListNode s2 = dummy2;
    
    		ListNode curr = list1;
    		int count = 0;
    		while (curr != null) {
    			if (count < a) {
    				s.next = curr;
    				s = s.next;
    			}
    			if (count > b) {
    				s2.next = curr;
    				s2 = s2.next;
    			}
    
    			curr = curr.next;
    			count++;
    		}
    		s2.next = null;
    
    		ListNode curr2 = list2;
    		while (curr2 != null) {
    			s.next = curr2;
    			curr2 = curr2.next;
    			s = s.next;
    
    		}
    
    		s.next = dummy2.next;
    		return dummy1.next;
    
    	}
    
    	public ListNode reverseBetween(ListNode head, int left, int right) {
    		Stack<ListNode> stk = new Stack<ListNode>();
    
    		if (head == null || head.next == null)
    			return head;
    		ListNode dummy1 = new ListNode(-1);
    		ListNode s = dummy1;
    
    		ListNode dummy2 = new ListNode(-1);
    		ListNode b = dummy2;
    
    		ListNode curr = head;
    		int count = 1;
    		while (curr != null) {
    			if (count < left) {
    				s.next = curr;
    				s = s.next;
    			}
    			if (count > right) {
    				b.next = curr;
    				b = b.next;
    			}
    			if (count >= left && count <= right) {
    				stk.push(curr);
    
    			}
    
    			curr = curr.next;
    			count++;
    		}
    		b.next = null;
    		while (!stk.isEmpty()) {
    			s.next = stk.pop();
    			s = s.next;
    		}
    
    		s.next = dummy2.next;
    		return dummy1.next;
    
    	}
    
    	public ListNode partition(ListNode head, int x) {
    		if (head == null || head.next == null)
    			return head;
    		ListNode dummy1 = new ListNode(-1);
    		ListNode s = dummy1;
    
    		ListNode dummy2 = new ListNode(-1);
    		ListNode b = dummy2;
    
    		ListNode curr = head;
    		while (curr != null) {
    			if (curr.val < x) {
    				s.next = curr;
    				s = s.next;
    			} else {
    				b.next = curr;
    				b = b.next;
    			}
    			curr = curr.next;
    		}
    		b.next = null;
    		s.next = dummy2.next;
    		return dummy1.next;
    	}
    
    	public ListNode rotateRight(ListNode head, int k) {
    		if (head == null) {
    			return head;
    		}
    		if (k == 0) {
    			return head;
    		}
    
    		int count = 0;
    		ListNode start = head;
    		// traverse till the end of the list and keep incrementing
    		// count
    		while (head.next != null) {
    			head = head.next;
    			count++;
    		}
    		count++;
    		// if k > count, do k%count, its an optimization. 2%5 == 12%5
    		k = k % count;
    		// find the new k
    		k = Math.abs(count - k);
    		if (k == 0)
    			return start;
    		// connect last element to start
    		head.next = start;
    		// traverse for new k value
    		while (k-- > 0) {
    			head = head.next;
    		}
    		// note: head is not the last element, so set the start.
    		start = head.next;
    		head.next = null;
    		return start;
    	}
    
    	public ListNode mergeKLists(ListNode[] lists) {
    		if (lists == null || lists.length == 0)
    			return null;
    
    		PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(
    				(Comparator<? super ListNode>) new Comparator<ListNode>() {
    					public int compare(ListNode l1, ListNode l2) {
    						return l1.val - l2.val;
    					}
    				});
    
    		ListNode head = new ListNode(0);
    		ListNode p = head;
    
    		for (ListNode list : lists) {
    			if (list != null)
    				queue.offer(list);
    		}
    
    		while (!queue.isEmpty()) {
    			ListNode n = queue.poll();
    			p.next = n;
    			p = p.next;
    
    			if (n.next != null)
    				queue.offer(n.next);
    		}
    
    		return head.next;
    
    	}
    
    	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    		if (l1 == null)
    			return l2;
    		if (l2 == null)
    			return l1;
    		if (l1.val < l2.val) {
    			l1.next = mergeTwoLists(l1.next, l2);
    			return l1;
    		} else {
    			l2.next = mergeTwoLists(l1, l2.next);
    			return l2;
    		}
    	}
    
    	public ListNode removeElements(ListNode head, int val) {
    		ListNode header = new ListNode(-1);
    		header.next = head;
    		ListNode cur = header;
    		while (cur.next != null) {
    			if (cur.next.val == val) {
    				cur.next = cur.next.next;
    			} else {
    				cur = cur.next;
    			}
    		}
    		return header.next;
    	}
    
    	void printList(ListNode node) {
    		while (node != null) {
    			System.out.print(node.val + " ");
    			node = node.next;
    		}
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    
    		ListNode list1 = new ListNode(0);
    		list1.next = new ListNode(1);
    		list1.next.next = new ListNode(2);
    		list1.next.next.next = new ListNode(3);
    		list1.next.next.next.next = new ListNode(4);
    		list1.next.next.next.next.next = new ListNode(5);
    
    		ListNode list2 = new ListNode(1000000);
    		list2.next = new ListNode(1000001);
    		list2.next.next = new ListNode(1000002);
    
    		int a = 3, b = 4;
    
    		sol.printList(sol.mergeInBetween(list1, a, b, list2));
    
    	}
    
    }

[c8af70495edc801909cd31d8772ddba1.png]: https://img-blog.csdnimg.cn/img_convert/c8af70495edc801909cd31d8772ddba1.png
[ee2696d40c6a78d51730772dbfc52657.png]: https://img-blog.csdnimg.cn/img_convert/ee2696d40c6a78d51730772dbfc52657.png
[f22bc506d9ae224be539ec6f98b19c06.png]: https://img-blog.csdnimg.cn/img_convert/f22bc506d9ae224be539ec6f98b19c06.png