当前位置: 首页 > 知识库问答 >
问题:

使用第三引用的两个链接列表的递归合并排序

冯霖
2023-03-14

我试图使用第三个引用来解决递归合并排序问题。我想引用第三个引用,继续按照排序顺序链接两个链表中的节点(两个链表分别排序),而不创建任何额外的节点。

我看到这里引用了一个递归程序。但是我想用第三个参考来尝试这个,但是我一直把它搞砸了。谁能告诉我我在这里缺少什么条件?

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的递归调用。根据需要纠正我和我的方法。

共有2个答案

茹高义
2023-03-14

如果你想要递归方法

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;
}
施自怡
2023-03-14

编辑:我刚刚又看了一遍,我认为修复代码的主要修改只是删除了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实现只使用链表而不使用任何数组的合并排序。但我陷入了一个逻辑错误;我的代码消除了一些输入并对剩余部分进行排序。我应用了三个类: