python怎么實(shí)現(xiàn)反轉(zhuǎn)鏈表

發(fā)布時(shí)間：2022-03-22 16:31:44 來源：億速云閱讀：164 作者：iii 欄目：大數(shù)據(jù)

這篇“python怎么實(shí)現(xiàn)反轉(zhuǎn)鏈表”文章的知識(shí)點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“python怎么實(shí)現(xiàn)反轉(zhuǎn)鏈表”文章吧。

【題目】

反轉(zhuǎn)一個(gè)單鏈表。

示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？

【思路】

使用三個(gè)指針p、q、r，指向三個(gè)相鄰的節(jié)點(diǎn)，其中p.next為q，q.next為r。

修改q的指針指向，并且移動(dòng)p、q、r三個(gè)指針，即q.next = p，p = q， q = r，r = r.next。不斷循環(huán)，并注意修改head.next及head，即可實(shí)現(xiàn)鏈表翻轉(zhuǎn)。

【代碼】

python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # head為空
        if not head:
            return head
        
        # p、q、r為相鄰三個(gè)節(jié)點(diǎn)
        # q.next指向p，同時(shí)三個(gè)指針后移
        p, q, r = head, head.next, head
        while q:
            r = q.next
            q.next = p
            p = q
            q = r
        
        # 修改head.next及head
        head.next = None
        head = p
        return p

以上就是關(guān)于“python怎么實(shí)現(xiàn)反轉(zhuǎn)鏈表”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對(duì)大家有幫助，若想了解更多相關(guān)的知識(shí)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細(xì)節(jié)

python怎么實(shí)現(xiàn)反轉(zhuǎn)鏈表

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽