leetcode1669-mergeLink

发布于:2024-05-23 ⋅ 阅读:(30) ⋅ 点赞:(0)

题目

给你两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除,并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果:
请你返回结果链表的头指针。
示例 1:
输入:list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出:[10,1,13,1000000,1000001,1000002,5]
解释:我们删除 list1 中下标为 3 和 4 的两个节点,并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

分析

这道题目思路比较直接,在list1中找到下标为a前面的结点,一直删除到下标为b的结点,list2中找到末尾结点,然后把list2插入进去

public class LinkNode {
	int val;
	LinkNode next;

	public LinkNode(int data) {
		this.val = data;
		this.next = null;
	}
}
public class LinkList {
	LinkNode head;
	public LinkList() {
		this.head = null;
	}
	public LinkNode getHead() {
		return this.head;
	}
	//添加元素
	public void addNode(int data) {
		LinkNode node = new LinkNode(data);
		if (this.head == null) {
			this.head = node;
		} else {
			LinkNode cur = this.head;
			while(cur.next != null) {
				cur = cur.next;
			}
			cur.next = node;
		}
	}
	//正序打印
	public void print(LinkNode node) {
		while(node != null) {
			System.out.print(node.val);
			System.out.print(" ");
			node = node.next;
		}
		System.out.println();
	}
	 public LinkNode mergeInBetween(LinkNode list1, int a, int b, LinkNode list2) {
        	LinkNode list2Tail = list2;
        	while(list2Tail.next != null) {
            		list2Tail = list2Tail.next;
        	}
        	int cur = 1;
        	LinkNode p = list1;
        	while(p != null) {
            		if(cur < a) {
                		p = p.next;
                		cur++;
            		} else {
				break;
			}
        	}
        	int diff = b - a + 1;
        	while(p.next != null && diff > 0) {
            		p.next = p.next.next;
            		diff--;
        	}
        	LinkNode tail = p.next;
        	p.next = list2;
        	list2Tail.next = tail;
		print(list1);
        	return list1;
    	}
}


public class mergeLink {
	public static void main(String[] args) {
		LinkList list1 = new LinkList();
		list1.addNode(10);
		list1.addNode(1);
		list1.addNode(13);
		list1.addNode(6);
		list1.addNode(9);
		list1.addNode(5);
		LinkList list2 = new LinkList();
		list2.addNode(1000000);
		list2.addNode(1000001);
		list2.addNode(1000002);
		list1.mergeInBetween(list1.getHead(),3,4,list2.getHead());
	}
}