题目
给你两个链表 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());
}
}