c++合并两个有序链表_合并无序链表?

有序链表的合并【python版】文章来源：LawsonAbs@CSDNLeetCode 链接

思路：

step1. 先比较两条链表谁的头结点对应的值最大，取较小的作为待返回的头结点step2. 依次比较两条链表，然后将小的值对应的结点放到结果链表末尾step3. 重复step2直到某条链表完成比较step4. 将未比较过的值直接链接到结果链表中

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, list1, list2): 
        h1 = list1
        h2 = list2
        if h1 is None :
            return h2
        if h2 is None:
            return h1
        
        # step1. 先确定头是谁
        start = h_res = None
        if h1.val <= h2.val :
            start = h1
            h1 = h1.next            
        else:
            start = h2
            h2 = h2.next            
        h_res = start

        # step2. 再依次遍历，合并两条链表
        while(h1 is not None and h2 is not None):
            if h1.val <= h2.val:
                tmp = h1.next # 保存
                h_res.next = h1
                h1 = tmp
            else:
                tmp = h2.next
                h_res.next = h2
                h2 = tmp            
            h_res = h_res.next            

        if h1 is not None:
            h_res.next = h1
        if h2 is not None:
            h_res.next = h2
        return start

node3 = ListNode(val=3,next = None)
node2 = ListNode(val=2,next = node3)
node1 = ListNode(val=1,next = node2)


node6 = ListNode(val=6,next = None)
node5 = ListNode(val=5,next = node6)
node4 = ListNode(val=2,next = node5)

s = Solution()
s.mergeTwoLists(node1,node4)