反转链表_

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

 输入：head = [1,2] 输出：[2,1]

示例 3：

输入：head = [] 输出：[]

示例代码：

#  define a linklist
class LinkNode(object):
    def __init__(self, val):
        self.val = val
        self.next = None


#  creat a linklist
def creat_linklist(li):
    if not li:
        print('This is an empty list')
        return
    head = p = LinkNode(li[0])

    for i in li[1:]:
        p.next = LinkNode(i)
        p = p.next
    return head


#  print a linklist
def print_linklist(head):
    if not head:
        print('This is an empty linklist!')
        return
    while head:
        print(head.val, end='->')
        head = head.next
    print("None")


#  reverse a linklist
def reverse_linklist(head):
    p_reverse_node = None
    p_node = head
    p_pre = None
    while p_node:
        p_next = p_node.next
        if not p_next:
            p_reverse_node = p_node
        p_node.next = p_pre
        p_pre = p_node
        p_node = p_next
    return p_reverse_node


# test
# 1. create link list
head = creat_linklist([1, 2, 3, 4, 5])
print_linklist(head)
# 2. reverse the link list
reverse = reverse_linklist(head)
# 3. print the link list
print_linklist(reverse)

运行效果：

【解题思路】：

1. 定义三个指针，一个指向当前，一个指向上一个节点，一个指向下一个节点；
2. 每次将当前节点的next指向上一个节点，并保存下一个节点；
3. 直到输出最后一个节点作为反转链表的头节点。

示例代码2：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = head
        pre = None
        while cur:
            p_next = cur.next
            cur.next = pre
            pre = cur
            cur = p_next
        return pre