Python怎么實現單鏈表中元素的反轉

這篇文章主要介紹了Python怎么實現單鏈表中元素的反轉的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Python怎么實現單鏈表中元素的反轉文章都會有所收獲，下面我們一起來看看吧。

給定一個單鏈表，將其反轉。其實很容易想到，只需要修改每個結點的指針指向:即令后一個結點指向前一個結點，并且將表頭指針指向最后一個結點即可。

這個過程可以用循環實現，也可以用遞歸來實現。

1、用循環來實現：

class LNode:
    def __init__(self, elem):
        self.elem = elem
        self.pnext = None
 
def reverse(head):
    if head is None or head.pnext is None: #如果輸入的鏈表是空或者只有一個結點，直接返回當前結點
        return head
    pre = None #用來指向上一個結點
    cur = newhead = head #cur是當前的結點。newhead指向當前新的頭結點
    while cur:
        newhead = cur
        temp = cur.pnext
        cur.pnext = pre #將當前的結點的指針指向前一個結點
        pre = cur
        cur = temp
    return newhead
 
if __name__=="__main__":
    head = LNode(1)
    p1 = LNode(2)
    p2 = LNode(3)
    head.pnext = p1
    p1.pnext = p2
    p = reverse(head)
    while p:
        print(p.elem)
        p = p.pnext

2、用遞歸來實現：

class LNode:
    def __init__(self, elem):
        self.elem = elem
        self.pnext = None
 
def reverse(head):
    if not head or not head.pnext:
        return head
    else:
        newhead = reverse(head.pnext)
        head.pnext.pnext = head #令下一個結點的指針指向當前結點
        head.pnext = None #斷開當前結點與下一個結點之間的指針指向聯系，令其指向空
        return newhead
 
 
if __name__=="__main__":
    head = LNode(1)
    p1 = LNode(2)
    p2 = LNode(3)
    head.pnext = p1
    p1.pnext = p2
    p = reverse(head)
    while p:
        print(p.elem)
        p = p.pnext

以下是圖解遞歸的詳細過程：

關于“Python怎么實現單鏈表中元素的反轉”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Python怎么實現單鏈表中元素的反轉”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。