剑指offer15：反转链表

思路(三指针法)

拿到一个题，首先得明白给定得条件和目的。

• 条件：一个链表，一般指单链表
• 目的：反转该链表、

再考虑特殊情况。

• 给定得链表为空时，怎么办(直接返回None)
• 对于该题目，还需要考虑当链表长度为1时得情况(返回pHead)

再考虑一般得思路。

• 要反转链表，最直接得想法就是头插法。我们可以新建立一个链表，用来存储要返回的头节点，但是题目中隐含要求头节点不能为空，所以不能新建链表，只能再原有的基础上进行操作。
• 不新建链表我们就需要三个指针
  p：指向原链表的第一个结点，也是新链表的尾结点，所以要在开始时置p.next=None
  q: q = p.next，用来执行头插的操作
  r：用来追踪原始链表
  三个指针每次循环时都向前移动，直到r.next = None,此时，需要再执行q.next = p的操作，最后一个结点加入新链表成为新链表的第一个结点。

# -*- 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
        
        if pHead == None:
            return None
        if pHead.next == None:
            return pHead
        
        p = pHead
        q = pHead.next
        r = pHead.next.next
        p.next = None
        while r:
            q.next = p
            p = q
            q = r
            r = r.next
        q.next = p
        return q           

时间复杂度

头插操作是O(1)，遍历操作是O(n),所以时间复杂度为O(n)