leetcode206 Reverse Linked List

 1 """
 2 Reverse a singly linked list.
 3 Example:
 4 Input: 1->2->3->4->5->NULL
 5 Output: 5->4->3->2->1->NULL
 6 """
 7 """
 8 自己的想法是头结点不动，转换后面的结点，结果成环了
 9 Wrong Answer
10 Your input
11 [1,2,3,4,5]
12 Output
13 Error - Found cycle in the ListNode
14 Expected
15 [5,4,3,2,1]
16 """
17 
18 class ListNode:
19     def __init__(self, x):
20         self.val = x
21         self.next = None
22 
23 class Solution:
24     def reverseList(self, head):
25         first = ListNode(0)
26         end = head.next
27         while end:
28             first.next = end
29             head.next = end.next
30             end.next = first.next
31             end = head.next
32         return first.next
33 
34 """
35 正确的做法，是先申请一个pre = None 作为尾结点
36 cur = head 作为当前结点，end = cur.next用来存储下一个需要更新的cur的位置
37 让当前的cur结点与pre相连cur.next = pre，并更新pre = cur, cur = end
38 返回pre
39 """
40 
41 class ListNode:
42     def __init__(self, x):
43         self.val = x
44         self.next = None
45 
46 class Solution:
47     def reverseList(self, head):
48         pre = None
49         cur = head
50         while cur:
51             end = cur.next
52             cur.next = pre
53             pre = cur
54             cur = end
55         return pre