【面试题15-反转链表】

剑指offer第十五题。

题目描述

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

解题思路

一开始学的时候看的答案就是这个方法，显然是要比递归好的，但是如果不理解的话，光靠背很容易出错，并且也不大背的上，如今重温这道题，其实是很简单的，我们下面用图示来阐述。

主要的思想是用两个指针，其中newHead指向的是反转成功的链表的头部，currentHead指向的是还没有反转的链表的头部：

初始状态是newHead指向null，currentHead指向的是第一个元素，一直往后遍历直到newHead指向最后一个元素为止：

下面展示的是其中某个时间点的指向细节：

理解了上面的图示，程序就呼之欲出了。

我的答案

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode newHead = null;
        ListNode currentHead = head;
        if(head == null || head.next == null){
            return head;
        }
        
        while(currentHead != null){
            ListNode next = currentHead.next;
            currentHead.next = newHead;
            newHead = currentHead;
            currentHead = next;
        }
        
        return newHead;
    }
}