关于链表:一周刷完剑指offer16合并两个有序的链表

合并两个有序的链表

1. 题目形容

输出两个枯燥递增的链表，输入两个链表合成后的链表，当然咱们须要合成后的链表满足枯燥不减规定。

2. 示例

无

3. 解题思路

思路：非递归

比拟两个链表的首结点，哪个小的的结点则合并到第三个链表尾结点，并向前挪动一个结点。

步骤一后果会有一个链表先遍历完结，或者没有

第三个链表尾结点指向残余未遍历完结的链表

返回第三个链表首结点

递归办法：

4. Java 实现

非递归的实现办法：应用一个辅助的头部节点：ListNode root = new ListNode(-1)

/*
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 node = new ListNode(-1); // 用于保留头部节点
        ListNode root = node;
        
        while (list1 != null && list2 != null){if (list1.val < list2.val){
                node.next = list1;
                node = node.next; // 更新 node 节点，指向下一个
                list1 = list1.next;
            }else{
                node.next = list2;
                node = node.next;
                list2 = list2.next;
            }
        }
                // 可能某个链表还残余值, 下列例子就链表 2 会残余
        // 比方链表 1：1->2->4
        // 链表 2：3->5->6
        if(list1 == null){node.next = list2;}
        
        if (list2 == null){node.next = list1;}
        return root.next;
        
    }
}

应用递归的实现办法：

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

5. Python 实现

比较简单的非递归的实现办法：

# 非递归实现合并两个有序的链表
class Solution1:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):    
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        
        start = None 
        p = None 
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                print(pHead1.val)
                if start is None:
                    start = p = pHead1
                else:
                    p.next = pHead1
                    p = p.next #更新 p 结点
                pHead1 = pHead1.next # 更新有序链表的结点
            else:
                if start is None:
                    start = p = pHead2
                else:
                    p.next = pHead2
                    p = p.next 
                pHead2 = pHead2.next 
        #可能某个链表始终还剩值
        if not pHead1: #如果第一个链表都是空的话
            p.next = pHead2
        else:
            p.next = pHead1
        return start 

应用递归的实现办法：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1: #如果一个链表不存在的话，返回另外一个链表
            return pHead2
        if not pHead2:
            return pHead1
        
        if pHead1.val <= pHead2.val:
            ret = pHead1
            ret.next = self.Merge(pHead1.next, pHead2)
        else:
            ret = pHead2
            ret.next = self.Merge(pHead1, pHead2.next)
            
        return ret 

如果您感觉本文有用，请点个“在看”