[CODE WAR記錄] 將Linked-List分成Front,Back2半的Linked-List(難度5)

[CODE WAR記錄] 將Linked-List分成Front,Back2半的Linked-List(難度5)

最近有點偷懶,沒有研究新的東西,blog鬧水荒,但是確實對於python的語法使用上還深深感到不足,因此還是來”高手村”練練功好了..,直接把codewar的練習結果與心得當作一篇好了XD

題目示例如下:

var source = 1 -> 3 -> 7 -> 8 -> 11 -> 12 -> 14 -> null
var front = new Node()
var back = new Node()
frontBackSplit(source, front, back)
front === 1 -> 3 -> 7 -> 8 -> null
back === 11 -> 12 -> 14 -> null

請建立frontBackSplit的程式碼

這個基礎的linked-list,竟然讓我卡最久的就是怎麼快速新增節點XD,原本我在想的是假如要完全不改動function的參數,到底要怎麼做到?

結果想太多,其實function要怎麼改都可以,只要最終驗證的function與介面是存在的,就好

後來我直接加上next的建構子,讓node可以這樣一次串起來…方便多了

    source = Node(1 ,Node(3, Node(7, Node(8, Node(11, Node(12, Node(14, None)))))))

 

後來我發現我的解法還在那邊想用遞迴,還加入了很多helper function,結果別人用幾個迴圈就寫完了…我真的太嫩了..

class Node( object ):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

def build_node_tree(node=None, master=True):
    link_msg = ""
    if isinstance(node, Node):
        if node.next != None:
            sub_node_msg = build_node_tree( node.next , False)
        else:
            sub_node_msg = " -> %s" % None
        if node.data != None:
            link_msg = "%s%s%s" % (" -> " , node.data, sub_node_msg)
    if master:
        return link_msg[3:]
    else:
        return link_msg

def node_count(node=None):
    count = 0
    if isinstance( node, Node ):
        if node.next != None:
            count += node_count(node.next)
        if node.data != None:
            count += 1
    return count

def add_node(node, data):
    if isinstance( node, Node ):
        if node.data != None and node.next != None:
            add_node(node.next, data)
        elif node.data != None and node.next == None:
            node.next = Node(data)
        else:
            node.data = data

def front_back_split(source, front, back, master=True):
    if source == None or front == None or back == None:
        raise Exception("error")
    if master:
        if node_count(source) <= 1:
          raise Exception("error")
        
    if isinstance( source, Node ):
        if source.data != None:
            x = node_count(source)
            y = node_count(front)
            if x > y:
                add_node( front, source.data)
            else:
                add_node( back, source.data )
        if source.next != None:
            front_back_split(source.next, front , back, False)

 

隨便挑的一個best practice..

class Node(object):
  def __init__(self, data = None, nxt = None):
    self.data, self.next = data, nxt
def front_back_split(source, front, back):
  if source is None or front is None or back is None or source.next is None: raise ValueError
  tortoise, hair = source, source
  while hair:
    if front.next: front = front.next
    front.data, front.next = tortoise.data, tortoise.next
    tortoise, hair = tortoise.next, hair.next.next if hair and hair.next else None
  front.next = None
  back.data, back.next = tortoise.data, tortoise.next

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

WP Facebook Auto Publish Powered By : XYZScripts.com