【第2題】 連結清單的逆置

連結清單是一個特殊的資料結構，其中每個節點包含自己的資料以及下一個值的引用（指針），連結清單的逆置就是指将連結清單下一個值的引用（指針）調換，如下圖所示：

第一步 構造連結清單

class Node(object):

    def __init__(self, value, next):
        self.value = value
        self.next = next


head = Node('頭', None)
last = head
for i in range(5):
    node = Node('v%s' % i, None)
    last.next = node
    last = node

# ######### 檢視連結清單關系 ##########
print('原始連結清單資訊為：')
print(head.value)
print(head.next.value)
print(head.next.next.value)
print(head.next.next.next.value)
print(head.next.next.next.next.value)
print(head.next.next.next.next.next.value)      

第二步 連結清單逆置

實作思路：

實作代碼：

def reverse_linked_list(head):
    """
    連結清單逆置
    :param head:
    :return:
    """
    if not head or not head.next:
        return head

    prev_node = None
    current_node = head
    next_node = head.next

    while True:
        current_node.next = prev_node
        if not next_node:
            break
        prev_node = current_node
        current_node = next_node
        next_node = current_node.next
    return current_node


new_head = reverse_linked_list(head)

print('逆置之後的連結清單')
print(new_head.value)
print(new_head.next.value)
print(new_head.next.next.value)
print(new_head.next.next.next.value)
print(new_head.next.next.next.next.value)
print(new_head.next.next.next.next.next.value)
      

　　

作者：武沛齊

出處：http://www.cnblogs.com/wupeiqi/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接。