剑指offer 合并两个排序链表

Posted on |

合并两个排序链表

题目

21.合并两个有序链表

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

方法

方法1：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# -*- 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
        head=ListNode(0)
        tail=head
        while pHead1 and pHead2:
            if pHead1.val<pHead2.val:
                tail.next=pHead1
                tail=pHead1
                pHead1=pHead1.next  # 这两句不换调换顺序
                tail.next=None      # 这两句不换调换顺序
            else:
                tail.next=pHead2
                tail=pHead2
                pHead2=pHead2.next  # 这两句不换调换顺序
                tail.next=None      # 这两句不换调换顺序
        if pHead1:
            tail.next=pHead1
        elif pHead2:
            tail.next=pHead2
        return head.next

方法2：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- 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 or not pHead2:
            return pHead2 or pHead1

        merge=ListNode(0)
        if pHead1.val<pHead2.val:
            merge=pHead1
            merge.next=self.Merge(pHead1.next,pHead2)
        else:
            merge=pHead2
            merge.next=self.Merge(pHead1,pHead2.next)
        return merge