【剑指Offer】25. 合并两个排序的链表

绝地灬酷狼 2022-11-26 01:53 109阅读 0赞

[NowCoder][]

## 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]

## 解题思路 ##

### 递归 ###

/* 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;
            
            if(list1.val <= list2.val) { 
                list1.next = Merge(list1.next, list2);
                return list1;
            }else { 
                list2.next = Merge(list1, list2.next);
                return list2;
            }
        }
    }

### 迭代 ###

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode Merge(ListNode list1,ListNode list2) { 
            ListNode head = new ListNode(-1);
            ListNode cur = head;
            
            while(list1 != null && list2 != null) { 
                if(list1.val <= list2.val) { 
                    cur.next = list1;
                    list1 = list1.next;
                }else { 
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            
            if(list1 != null)
                cur.next = list1;
            if(list2 != null)
                cur.next = list2;
            
              
            
            return head.next;
        }
    }

[NowCoder]: https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys@163.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]: /images/20221124/2d82ea75e5bc4916a714404800de1a14.png