leetcode 206. 反转链表（Java）

链表反转示意图如下：

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

思路：从头结点开始一个个节点反转，反转每个节点时需要保存自身节点引用backward和自身的下一个节点引用forward，保存好之后，则反转当前节点。然后开始第二个节点的反转，即迁移自身到原来的下一个节点，即与forward指向同一个节点，此时可以前移forward到下一个节点，即第三个节点。然后反转当前节点（即第二个节点）指向前一个节点backward（即第一个节点），并前移backward指向当前节点（即第二个节点），此时第二个节点反转完成。

接着以以上步骤继续反转第三个节点，直到尾节点，源码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        
        // 反转每个节点时，需要保存当前节点和当前节点的下一个节点后，才对当前节点进行反转
        ListNode backward = head;
        ListNode forwad =  head.next;
        
        // 此时可以反转head的next为null了
        head.next = null;
        
        while (forwad != null) {
            head = forwad; // head执行原先的head.next
            forwad = head.next; // forward指向head.next.next
            
            // 此时实现head.next的反转，指向head
            head.next = backward; // head.next执行head，完成了head.next的反转
            backward = head; // backward执行head.next
        }
        return head;
    }
}