[数据结构与算法]力扣206.反转链表(Java解法)

题目：给你单链表的头节点?head?，请你反转链表，并返回反转后的链表。

?这题反复做过好多次，这次将自己的思路总结后记录下来。

思路一：（双指针）

用双指针改变原链表中的指针的指向即可。初始化一个指针cur指向头结点head，初始化一个指针pre指向空。

ListNode cur = head;
ListNode pre = null;

其中cur负责遍历链表，而pre则负责指向链表反转后的头结点。如下图为整个迭代过程：

初始时pre指向null，cur指向head。如下图：

这里分为4步完成一次迭代：

（1）保存cur的下一个结点为temp；

            temp = cur.next;

（2）将cur的下一个结点指向pre；

            cur.next = pre;

到这里已经完成了第一个结点的反转。接下来是将pre和cue同时向后移动，准备下一步的迭代。

（3）pre指向cur；

            pre = cur;

（4）cur指向事先保存的结点temp，也就是向后移动一位的意思。

            cur = temp;

经过一次迭代后，链表的指针指向变为如下图所示：

?

到这里可以发现，仅仅是从图上来说，pre始终在cur的前面一个位置。实际上cur.next=pre。当cur为空时，说明已经迭代完整个链表，可得出迭代的终止条件为cur == null。

当整个链表迭代完后如下图：此时cur指向空，说明链表迭代结束。

?

具体的迭代代码为：

temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;

最后完整的代码为：

    public ListNode reverseList(ListNode head) {
        ListNode temp;
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

这仅仅是其中的一种解法，还包括递归法。后续会补充！