翻轉一個鏈表
樣例：給出一個鏈表1->2->3->null，這個翻轉后的鏈表為3->2->1->null
一種比較簡單的方法是用“摘除法”。就是先新建一個空節點，然后遍歷整個鏈表，依次令遍歷到的節點指向新建鏈表的頭節點。
那樣例來說，步驟是這樣的：
1. 新建空節點：None
2. 1->None
3. 2->1->None
4. 3->2->1->None
代碼就非常簡單了：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
""" 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 |
當然，還有一種稍微難度大一點的解法。我們可以對鏈表中節點依次摘鏈和鏈接的方法寫出原地翻轉的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
""" 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 # 把摘鏈的地方連起來 pre.next = cur.next cur = pre.next temp.next = dummy.next dummy.next = temp return dummy.next # write your code here |
需要注意的是，做摘鏈的時候，不要忘了把摘除的地方再連起來
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
