[数据结构与算法]【LeetCode】反转链表

206 反转链表?

示例:

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

思路：

1、定义指针pre和cur指针，pre指针用来指向前驱节点，cur指针用来遍历整个链表，初始化pre = null，cur = head。
2、首先用一个临时节点tmp保存cur指针节点的后继节点(ListNode tmp= curr.next;) ，然后让cur指针节点的next指针指向其前驱节点(cur.next = pre)，最后pre指针和cur指针分别后移一位(prev = curr;? curr = next;)

3、重复上述过程，直到cur指向空节点。

4、最后返回pre节点。

(动图来自网络)?

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null)
        {
            ListNode tmp = cur.next;  //tmp保留cur的后继节点
            cur.next = pre;         //cur指向前驱节点
            pre = cur;         //pre和cur节点前进一位
            cur = tmp;
        }
        return pre;					//最后返回pre
    }
}