翻转一个链表
样例:给出一个链表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
|
需要注意的是,做摘链的时候,不要忘了把摘除的地方再连起来
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!