[数据结构与算法]剑指 Offer 24. 反转链表

剑指 Offer 24. 反转链表

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

示例:

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

限制：

0 <= 节点个数 <= 5000

这个问题，首先考虑采用双指针一前一后从头往后遍历整个列表，依次将每两个节点间的指针反转。

但是存在以下问题：

问题一：当前面指针的next指向了后面指针后，无法继续向前遍历了，如下图。

因此在反转指针之前，需要一个变量保存前面指针的next的值。

问题二：

循环结束条件的设定：

如下图，如果设置初始值p=null. Q =head X = head.next

那么很容易写成如下的循环条件：

 while(q != null){
            q.next = p;
            p = q;
            q = x;
            x = x.next;
        }

当Q到列表的最后一个节点的时候，依然会进入循环体，此时Q==null ,可x却成为了一个空指针，这个时候就会报空指针异常。

java.lang.NullPointerException
  at line 17, Solution.reverseList
  at line 57, __DriverSolution__.__helper__
  at line 82, __Driver__.main

所以做如下改进：

只有当我们判定Q！=null的情况下，我们才会给X赋值为Q.next，这样就避免了X出现空指针的情况。

代码如下：

/**
 * 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 p = null,q = head;

        while(q != null){
            ListNode x = q.next;
            q.next = p;
            p = q;
            q = x;
        }
        return p;
    }
}

可以看到 ，只有当q不为null的情况下 我们才会给x赋值为q.next，以此来记录q原本下一个节点的位置。

最后的状态是：P指向了最后一个节点，Q指向了null。我们只需要返回指针P即可。