1 单向链表的反转
问题描述：
给定一个带头结点的单链表，请将其逆序。即如果单链表原来为head -->1 --> 2 --> 3 --> 4 --> 5，那么逆序后变为head --> 5 --> 4 --> 3 --> 2 --> 1。
解决过程：
给定一个单向链表1-->2-->3，通过下面的示意图，看如何一步一步的将单向列表反转。
代码实现：
1 class Node(object):
2 def __init__(self, data):
3 self.data = data
4 self.next = None
5
6 def createSingleLink():
7 head = Node(1)
8 cur = head
9 for i in range(2, 10):
10 cur.next = Node(i)
11 cur = cur.next
12 return head
13
14 def printSingleLink(head):
15 cur = head
16 while cur is not None:
17 print(cur.data, end='')
18 if cur.next is not None:
19 print("-->", end='')
20 cur = cur.next
21
22 def Reverse(head):
23 pre = None
24 cur = head
25 while cur is not None:
26 next_ = cur.next
27 cur.next = pre
28 pre = cur
29 cur = next_
30 return pre
31
32 if __name__ == '__main__':
33 singleHead = createSingleLink()
34 printSingleLink(singleHead)
35 reverSingleHead = Reverse(singleHead)
36 print()
37 printSingleLink(reverSingleHead)
View Code
2 双向链表反转
问题描述：
给定一个带头结点的双向链表，请将其逆序。即如果单链表原来为head -->1 --> 2 --> 3 --> 4 --> 5，那么逆序后变为head --> 5 --> 4 --> 3 --> 2 --> 1。
解决过程：
例如，给定一个带头结点的双向链表1-->2-->3，如下图看如何一步一步进行反转：
代码实现：
1 class Node(object):
2 def __init__(self, data):
3 self.last = None
4 self.data = data
5 self.next = None
6
7 def creatDoubleLink():
8 head = Node(1)
9 cur = head
10 for i in range(2, 10):
11 cur.next = Node(i)
12 Node(i).last = cur
13 cur = cur.next
14 return head
15
16 def printDoubleLink(head):
17 cur = head
18 while cur:
19 print(cur.data, end='')
20 if cur.next:
21 print("-->", end='')
22 cur = cur.next
23
24 def Reverse(head):
25 pre = None
26 cur = head
27 next_ = None
28 while cur:
29 next_ = cur.next
30 cur.next = pre
31 cur.last = next_
32 pre = cur
33 cur = next_
34 return pre
35
36 if __name__ == '__main__':
37 doubleHead = creatDoubleLink()
38 printDoubleLink(doubleHead)
39 reveDoubleHead = Reverse(doubleHead)
40 print()
41 printDoubleLink(reveDoubleHead)
View Code
3 总结：
单向链表和双向链表的反转比较简单，只需做到代码一次成型，运行不出错即可。上述两种代码的实现过程，都是对原有的链表进行遍历，所以如果链表长度为N，那么它们的时间复杂度和空间复杂度为O(N)和O(1)。