数据结构
- 1.合并两个有序数组
- 代码:
1.合并两个有序数组
这里我们可以创建一个新的对象作为合并后的新链表newHead,而NewHead.next就是我们要返回的头部的位置
在创建一个对象来获取nextHead.next下一个节点来作为我们新链表的起始位置防止我们的头部位置找不到
循环条件为list1与list2均不为null,开始比较list1和list2中的大小,如果是最小值将其放入nextHead的数组中,然后list1走到下一个节点继续与list2匹配,每次都将最小值或相等值放入合并的链表中
链表每次放入数据要切换到下一个节点
这里list1已经走到了最后一个位置,走下去为空,当list1为空后,跳出循环
然后将list2的目标节点放入nextHead.next中
代码:
/**
* 将两个升序的链表合并成一个升序链表
* 这里我们可以创建一个新的对象作为合并后的新链表newHead,而NewHead.next就是我们要返回的头部的位置
* 在创建一个对象来获取nextHead.next下一个节点来作为我们新链表的起始位置防止我们的头部位置找不到
* list1和list2两个一起走来进行大小比较,如果list1小就将list1放入nextHead中然后list1切换到下一个节点,当list2小时或者是等于,这里需要规定好条件,如果等于的话条件不满足会造成死循环,这里条件出去我们的nextHead.next切换到下一个节点在进行比较,while循环设置为list1与list2均不等于null,当list1先走完,while循环结束判断两者谁不为null,不为null的链表将它放在nextHead.next中
* 然后返回newHead.next
* @return
*/
public static MyLinkedList.NodeList mergeTwoLists(MyLinkedList.NodeList node1, MyLinkedList.NodeList node2){
MyLinkedList.NodeList newHead =new MyLinkedList.NodeList(0);
MyLinkedList.NodeList NextHead =newHead;
while(node1!=null&&node2!=null){
if(node1.value>node2.value){
NextHead.next=node2;
node2=node2.next;
}else{
NextHead.next=node1;
node1=node1.next;
}
NextHead=NextHead.next;
}
if(node1!=null){
NextHead.next=node1;
}
if(node2!=null){
NextHead.next=node2;
}
return newHead.next;
}