剣指offer面接問題25:2つのソートされたチェーンテーブルをマージ(python実装)

2つのソートされたチェーンテーブルをマージ(python実装)
一、テーマの説明
テーマ:2つのソートされたチェーンテーブルをマージ2つのインクリメンタルソートされたチェーンテーブルを入力し、この2つのチェーンテーブルをマージし、新しいチェーンテーブルのノードをインクリメンタルにします.
二、問題を解く構想
  暫略.(ここでは主に本のpythonとして補完する)
三、コード実装
ここでのチェーンテーブルは一方向チェーンテーブルであり、プログラムをより直感的に示すために、まずノードクラスを定義します.以下のようにします.

class LinkedListNode():
    def __init__ (self, value = None, next = None):
        self.value = value
        self.next = next

次に、一方向チェーンテーブルの操作に詳しい場合は、一時的に無視できますが、この部分をスキップしても後続のプログラムの理解に影響しません.使用するクラス関数を含め、一方向チェーンテーブルの操作については、一方向チェーンテーブルの作成と基本的な操作が表示されます.

#     
class SingleLinkedList():
    #    
    def __init__ (self):
        self.head = None

    #         
    def is_empty(self):
        if self.head is None:
            return True
  
    #         
    def append(self,new_value):
        node = LinkedListNode(new_value)
        if self.is_empty():
            self.head = node
        else:
            node.next = self.head
            self.head = node
    
    #       ，           
    def travel(self):
        cur = self.head
        ls = []
        while cur is not None:
            ls.append(cur.value)
            cur =cur.next
        return ls
        
    #        ，    ，               
    def travelSetHead(self,pHead):
        cur = pHead
        ls = []
        while cur is not None:
            ls.append(cur.value)
            cur =cur.next
        return ls

このブログの主な部分:Pythonがテーマを実現するために要求したプログラムは以下の通りです.

def merge2LinkedList(pHead1,pHead2):
    if pHead1 is None and pHead2 is None:
        return
    elif pHead1 is None:
        return pHead2
    elif pHead2 is None:
        return pHead1
    pMergeHead = LinkedListNode()
    if pHead1.value < pHead2.value:
        pMergeHead = pHead1
        pMergeHead.next = merge2LinkedList(pHead1.next,pHead2)
    else:
        pMergeHead = pHead2
        pMergeHead.next = merge2LinkedList(pHead1,pHead2.next)
    return pMergeHead

2つのチェーンテーブルをインスタンス化し、次のようにチェーンテーブルノードを追加する一連の操作を行います.

>>> SLL1 = SingleLinkedList()
>>> for i in range(10,1,-2):
    	SLL1.append(i)
>>> print(SLL1.travel())

>>> SLL2 = SingleLinkedList()
>>> for i in range(5,0,-2):
    	SLL2.append(i)
>>> print(SLL2.travel())

Out:
[2, 4, 6, 8, 10]
[1, 3, 5]

>>> pMergeHead = merge2LinkedList(SLL1.head,SLL2.head)
>>> SLL1.travelSetHead(pMergeHead)

Out:
[1, 2, 3, 4, 5, 6, 8, 10]

もちろん,プログラム実装のロバスト性を高めるために,ここではいくつかの特殊な入力状況を考慮した.
インスタンス化SLL 2は、以下のように空のチェーンテーブルである.

>>> SLL1 = SingleLinkedList()
>>> for i in range(10,1,-2):
    	SLL1.append(i)
>>> print(SLL1.travel())

>>> SLL2 = SingleLinkedList()
>>> print(SLL2.travel())

Out:
[2, 4, 6, 8, 10]
[]

  このとき合併した後、元のSLL 1チェーンテーブルであるべきで、以下の通りである.

pMergeHead = merge2LinkedList(SLL1.head,SLL2.head)
SLL1.travelSetHead(pMergeHead)

Out:
[2, 4, 6, 8, 10]