问题描述

Reverse a singly linked list.

补充说明：

这个题目简单粗暴，就是让你把一个单链表进行翻转。举个栗子：
单链表1>3>4>2翻转后的结果为2>4>3>1。

方案分析

1. 链表的操作估计大家都会，自然而然的想到的肯定是相邻两个节点之间的交换问题，能想到这一步已经成功了三分之一了。
2. 现在继续分析，确定翻转链表需要几个指针。head指针，这个毋庸置疑。cur_node:当前操作的指针, next_node:当前操作指针的下一个指针。这里这个必须，否则在操作cur_node指针的时候无法找到后续的节点了。
3. 交换链表元素相信大家都会，但是这里有个问题，cur_node.next=next_node.next这步骤肯定不能缺失，那另外一个指针付给谁，cur_node? No，应该给head。Why？ 大白话来讲就是，一言不合扔到最前端。参见我画的流程图：翻转流程.

python实现

# !-*- coding:utf8 -*-
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        # 长度超过两位
        cur_node = head
        next_node = head.next
        while(next_node is not None):
            cur_node.next = next_node.next
            next_node.next = head
            head = next_node
            next_node = cur_node.next
        return head