反转链表

输入一个链表，反转链表后，输出新链表的表头。

解题思路

暴力求解：

1. 先用数组res存一遍所有的值；
2. 然后再构建一个链表。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        res=[]
        if pHead is None or pHead.next is None:
            return pHead
        while pHead.next:
            res.append(pHead.val)
            pHead=pHead.next
        #res.append(pHead.val)
        r = rHead = ListNode(pHead.val)
        for i in range(len(res)):
            rHead.next=ListNode(res.pop())
            rHead=rHead.next
        rHead.next=None
        return r #注意这里是返回头

使用三个指针完成，参考这篇博客的图示，很清楚！！！

注意最后一步，当没有第三个指针时，要在循环外赋值，不然会少一个数！

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        res=[]
        if pHead is None or pHead.next is None:
            return pHead
        first=pHead
        second=pHead.next
        pHead.next=None
        while second.next:
            third=second.next
            second.next=first
            first=second
            second=third
        second.next=first
        first=second
        return first