欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指Offer_编程题_合并两个排序的链表

程序员文章站 2022-07-01 15:42:54
剑指Offer_编程题_合并两个排序的链表 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 题目答案,思路 https://www.nowcoder.com/questionTerminal/d8b6b4358f774294a89de2a6ac ......

剑指offer_编程题_合并两个排序的链表

 

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
 

题目答案,思路

https://www.nowcoder.com/questionterminal/d8b6b4358f774294a89de2a6ac4d9337?f=discussion

递归版本

链接:https://www.nowcoder.com/questionterminal/d8b6b4358f774294a89de2a6ac4d9337?f=discussion
来源:牛客网

public listnode merge(listnode list1,listnode list2) {
       if(list1 == null){
           return list2;
       }
       if(list2 == null){
           return list1;
       }
       if(list1.val <= list2.val){
           list1.next = merge(list1.next, list2);
           return list1;
       }else{
           list2.next = merge(list1, list2.next);
           return list2;
       }       
   }

非递归版本

public class solution {
    public listnode merge(listnode list1,listnode list2) {
    listnode  root = new listnode(-1);
        //临时指向的节点,可以理解为临时的 root 尾节点
        listnode last = root;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                //重新
                last.next=list1;
                last = list1;
                list1 = list1.next;
            } else {
                last.next = list2;
                last = list2;
                list2 = list2.next;
            }
        }
        //把未结束的链表连接到合并后的链表尾部
        if (list1 != null) {
            last.next = list1;
        }
        if (list2 != null) {
            last.next = list2;
        }
        return root.next;
    }
}

 

 

测试代码

public class listnode {
    int val;
    listnode next = null;

    listnode(int val) {
        this.val = val;
    }
}


public class testlistnode {

    //        链接:https://www.nowcoder.com/questionterminal/d8b6b4358f774294a89de2a6ac4d9337?f=discussion
//        来源:牛客网
//尾插法创建单链表  队列形式先进先出
    public void back(listnode node, int data) {
        if (data < 10) {
            listnode next = new listnode(data);
            next.val = data;
            next.next = null;
            node.next = next;
            back(next,data+3);
        }
    }

    public void back2(listnode node, int data) {
        if (data < 10) {
            listnode next = new listnode(data);
            next.next = null;
            node.next = next;
            back2(next, data=data+2);
        }
    }



    public static void main(string[] args) {
         listnode headnode;
         listnode headnode2;
        testlistnode list1 = new testlistnode();
        headnode = new listnode(3);//头指针
        list1.back(headnode, 4);//后插法

        system.out.println("创建后的链表是:");
//        while (headnode.next != null) {
//            headnode = headnode.next;
//            system.out.print(headnode.val + " ");
//        }
        system.out.println("-----------------------------");
        testlistnode list2 = new testlistnode();
        headnode2 = new listnode(4);//头指针
        list2.back2(headnode2, 5);//后插法


        system.out.println("创建后的链表是:");
//        while (headnode2.next != null) {
//            headnode2 = headnode2.next;
//            system.out.print(headnode2.val + " ");
//        }

        listnode merged=  new solution().merge(headnode,headnode2);

        system.out.println("merge :");
        while (merged.next != null) {
            merged = merged.next;
            system.out.print(merged.val + " ");
        }

    }

}