我试图使用第三个引用来解决递归合并排序问题。我想引用第三个引用,继续按照排序顺序链接两个链表中的节点(两个链表分别排序),而不创建任何额外的节点。
我看到这里引用了一个递归程序。但是我想用第三个参考来尝试这个,但是我一直把它搞砸了。谁能告诉我我在这里缺少什么条件?
import java.util.ArrayList;
import java.util.ListIterator;
public class MergeLinkedListsIntoExisting {
public static void main(String[] args){
Node nodeList1 = null, nodeList2 = null;
Node temp = null;
ArrayList<Integer> array1 = new ArrayList<Integer>();
array1.add(3);
array1.add(7);
array1.add(9);
ArrayList<Integer> array2 = new ArrayList<Integer>();
array2.add(1);
array2.add(2);
array2.add(8);
nodeList1 = add(nodeList1, array1);
nodeList2 = add(nodeList2, array2);
System.out.println("**List 1**");
print(nodeList1);
System.out.println("**List 2**");
print(nodeList2);
System.out.println("Sorted List");
Node nodeList3 = mergeTwoLists(nodeList1, nodeList2, temp);
print(nodeList3);
}
private static Node add(Node node, ArrayList<Integer> list){
Node current = node;
Node head = node;
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
if(head==null){
head = new Node();
head.data = it.next();
head.next=null;
node = head;
}
else{
current = new Node();
current.data = it.next();
current.next = null;
node.next = current;
node = node.next;
}
}
return head;
}
private static void print(Node node) {
if(node!=null){
while(node.next!=null){
System.out.print(node.data + " ");
node = node.next;
}
System.out.println(node.data);
}
else{
System.out.println("No elements in the linkedList.");
}
}
private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
if(nodeList1 == null) return nodeList2;
if(nodeList2 == null) return nodeList1;
if(nodeList1.data <= nodeList2.data){
if(temp == null){
temp = nodeList1;
temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp.next);
}
else{
System.out.println(temp.data);
temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp.next);
}
}else{
if(temp == null){
temp = nodeList2;
System.out.println(temp.data);
temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp.next);
}
else{
System.out.println(temp.data);
temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp.next);
}
}
return temp;
}
}
分辨率应与temp一致。接下来是MergeTwoList的递归调用。根据需要纠正我和我的方法。
如果你想要递归方法
private static Node mergeTwoLists(Node nodeList1, Node nodeList2) {
if(nodeList1 == null) return nodeList2;
if(nodeList2 == null) return nodeList1;
Node tmp = new Node();
if(nodeList1.data <= nodeList2.data){
tmp.data = nodeList1.data;
tmp.next = mergeTwoLists(nodeList1.next, nodeList2);
}else{
tmp.data = nodeList2.data;
tmp.next = mergeTwoLists(nodeList1, nodeList2.next);
}
return temp;
}
编辑:我刚刚又看了一遍,我认为修复代码的主要修改只是删除了temp=null的特殊情况。
我刚刚修改了你的代码,让它正常工作。只需通过temp
而不是temp。接下来
,如果temp为null,则不需要特殊情况。
import java.util.ArrayList;
import java.util.ListIterator;
public class MergeLinkedListsIntoExisting {
public static void main(String[] args){
Node nodeList1 = null, nodeList2 = null;
Node temp = null;
ArrayList<Integer> array1 = new ArrayList<Integer>();
array1.add(3);
array1.add(7);
array1.add(9);
ArrayList<Integer> array2 = new ArrayList<Integer>();
array2.add(1);
array2.add(2);
array2.add(8);
nodeList1 = add(nodeList1, array1);
nodeList2 = add(nodeList2, array2);
System.out.println("**List 1**");
print(nodeList1);
System.out.println("**List 2**");
print(nodeList2);
System.out.println("Sorted List");
Node nodeList3 = mergeTwoLists(nodeList1, nodeList2, temp);
print(nodeList3);
}
private static Node add(Node node, ArrayList<Integer> list){
Node current = node;
Node head = node;
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
if(head==null){
head = new Node();
head.data = it.next();
head.next=null;
node = head;
}
else{
current = new Node();
current.data = it.next();
current.next = null;
node.next = current;
node = node.next;
}
}
return head;
}
private static void print(Node node) {
if(node!=null){
while(node.next!=null){
System.out.print(node.data + " ");
node = node.next;
}
System.out.println(node.data);
}
else{
System.out.println("No elements in the linkedList.");
}
}
private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) {
if(nodeList1 == null) return nodeList2;
if(nodeList2 == null) return nodeList1;
if(nodeList1.data <= nodeList2.data){
temp = nodeList1;
temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp);
}else{
temp = nodeList2;
temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp);
}
return temp;
}
}
public class Node{
int data;
Node next;
}
NowCoder 题目描述 解题思路 递归 // java public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.val <= lis
假设列表“A”是1- 请回顾一下这个,帮我即兴创作
最后一个函数返回15->20,然后组合为root.next->temp,但是在返回temp的步骤之后,为什么会返回根值。即10->15->20,而我希望只返回temp。 请找到代码,
我有一个关于python中链接列表的快速问题。在下面显示的解决方案代码中,当我尝试合并两个排序的链接列表时。我对包含的if和elif语句的条件感到困惑。例如,如果l1不为空,l2为空,我想将l1中的其余3个元素添加到我的新链接列表中,但代码显示l1和tail没有更新,所以它不是只添加3个元素中的一个吗? 我的另一个问题是关于返回head.next.返回会自动返回从head.next到null pt
一、题目 输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。 二、解题思路 Step1.定义一个指向新链表的指针,暂且让它指向NULL; Step2.比较两个链表的头结点,让较小的头结点作为新链表的头结点; Step3.有两种方法。 ①递归比较两个链表的其余节点,让较小的节点作为上一个新节点的后一个节点; ②循环比较两个链表的其余节点,让较小的节点作为上一个新节点的后一
我想使用java实现只使用链表而不使用任何数组的合并排序。但我陷入了一个逻辑错误;我的代码消除了一些输入并对剩余部分进行排序。我应用了三个类: