面试题24. 反转链表

题目描述：

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

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

思路：

可以这么看，更好理解
输入: 1->2->3->4->5->NULL
输出: NULL<-1<-2<-3<-4<-5
1. 利用双指针，cur指向新链表的头结点（开始为NULL）  pre代表原链表的头节点（初始值Head），从原链表头结点开始遍历
2. 反转链表，要让1的next指指向NULL（pre.next = cur），那么1->2就会断开，所以我们需要先暂存 tmp = pre.next；接着我们将pre.next 指向cur，cur变成指向pre，而pre指向tmp，我们暂存的节点。
3.当原链表遍历完之后结束。

python3解法：

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        cur = None
        pre = head
        while pre:
            tmp = pre.next
            pre.next = cur
            cur = pre
            pre = tmp
        return cur

Java解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode currentNode = head;
        ListNode reverseHead = null;
        ListNode preNode = null;
        while(currentNode != null)
        {
            ListNode nextNode = currentNode.next;
            if ( nextNode == null) reverseHead = currentNode;
            currentNode.next = preNode;
            preNode = currentNode;
            currentNode = nextNode;
        }
        return reverseHead;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/fan-zhuan-lian-biao-yi-dong-de-shuang-zhi-zhen-jia/