牛客网-合并两个排序的链表

ゝ一世哀愁。 2023-03-01 09:06 16阅读 0赞

# 题目描述 #

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

# 解法1 歪门邪道 #

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    import java.util.List;
    import java.util.ArrayList;
    import java.util.Collections;
    
    public class Solution { 
        public ListNode Merge(ListNode list1,ListNode list2) { 
             List<Integer> list = new ArrayList<>();
    
            while (list1!=null){ 
                list.add(list1.val);
                list1=list1.next;
            }
    
            while (list2!=null){ 
                list.add(list2.val);
                list2=list2.next;
            }
    
            //排序 １　<　２　< ３　< ４ 递增的顺序
            Collections.sort(list);
    
            ListNode
                    head=null,//头
                    tail=null,//尾
                    newnode=null;//每次创建的新节点
    
            for (int i = 0; i < list.size(); i++) { 
    
                //创建新的节点
                newnode=new ListNode(list.get(i));
    
                //如果是第一个节点,就选创建出来头节点
                if(i==0){ 
                    head =tail= newnode;
                }else{ 
                    //如果不是最后一个节点就往next添加节点
                    tail.next = newnode;
                    tail=newnode;
    
                }
            }
    
            return head;
        }
    }

# 解法2 非递归 #

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode Merge(ListNode list1,ListNode list2) { 
            
            //合并前先判断一下两个链表是否为空，如果单个为空就直接返回
            if(list1==null)
                return list2;
            if(list2==null)
                return list1;
            
            
            /* 合并中，无非就是比较各自首节点谁小，就把该节点从原链表中删除，在尾插到新节点处。 比较中，两个链表任何一个都不能为空。 */
            ListNode head = null;
            ListNode end = null;
            
            //只有两个都不为空的时候，才同时进行比较
            while(list1!=null && list2!=null){ 
                //比较，找到节点小的一个
                ListNode p = list1.val < list2.val ? list1 : list2;
                //如果这个小的节点是list1，那么list1就往后走一个
                if( list1 == p){ 
                    list1 = list1.next;
                }else{ 
                    //否则list2就往后走
                    list2 = list2.next;
                }
                
                //判断是否是第一次，如果是第一次合并的话，就不能往.next处放，直接赋值就可
                if(head == null){ 
                    head = p;
                    end = p;
                }else{ 
                    end.next=p;
                    end=p;
                }
                
            }
            
            /* 合并之后，可能会存在这么三种情况： 1、list1为空，但是list2不为空； 2、list1不为空，但是list2为空； 3、list1和list2都为空。 需要针对这三种情况做处理 */
            
            if(list1 == null){ 
                end.next = list2;
            }
            
            if(list2==null){ 
                end.next = list1;
            }
            
            
            return head;
            
            
            
        }
    }

# 解法3 递归法 #

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode Merge(ListNode list1,ListNode list2) { 
            
            if(list1==null)
                return list2;
            if(list2==null)
                return list1;
            //合并中，找到第一个小的节点 
            ListNode newNode = null;
            if(list1.val < list2.val){ 
                newNode = list1;
                list1 = list1.next;
            }else{ 
                newNode = list2;
                list2 = list2.next;
            }
            
            //合并剩下的节点
            newNode.next = Merge(list1,list2);
           
            return newNode;
        }
    }