翻轉(zhuǎn)一個(gè)鏈表
樣例：給出一個(gè)鏈表1->2->3->null，這個(gè)翻轉(zhuǎn)后的鏈表為3->2->1->null
一種比較簡(jiǎn)單的方法是用“摘除法”。就是先新建一個(gè)空節(jié)點(diǎn)，然后遍歷整個(gè)鏈表，依次令遍歷到的節(jié)點(diǎn)指向新建鏈表的頭節(jié)點(diǎn)。
那樣例來(lái)說(shuō)，步驟是這樣的：
1. 新建空節(jié)點(diǎn)：None
2. 1->None
3. 2->1->None
4. 3->2->1->None
代碼就非常簡(jiǎn)單了：
""" Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: The first node of the linked list. @return: You should return the head of the reversed linked list. Reverse it in-place. """ def reverse(self, head): temp = None while head: cur = head.next head.next = temp temp = head head = cur return temp # write your code here
當(dāng)然，還有一種稍微難度大一點(diǎn)的解法。我們可以對(duì)鏈表中節(jié)點(diǎn)依次摘鏈和鏈接的方法寫(xiě)出原地翻轉(zhuǎn)的代碼：
""" Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: The first node of the linked list. @return: You should return the head of the reversed linked list. Reverse it in-place. """ def reverse(self, head): if head is None: return head dummy = ListNode(-1) dummy.next = head pre, cur = head, head.next while cur: temp = cur # 把摘鏈的地方連起來(lái) pre.next = cur.next cur = pre.next temp.next = dummy.next dummy.next = temp return dummy.next # write your code here
需要注意的是，做摘鏈的時(shí)候，不要忘了把摘除的地方再連起來(lái)
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
新聞熱點(diǎn)
疑難解答
圖片精選
