题解 | #反转链表#

单链表反转：

双指针实现

图一

1.如图一定义两个指针并初始化指针；当前指针cur执行头结点，pre指针表示头结点的前一个结点，很明显此时pre=null

图二

2.如图二cur.next指向pre(cur.next=pre)头指针进行反转指向了前一个，pre指向cur(pre=cur)，pre移动到原来的cur的位置。但是此时有个位置，链表已经断开了，导致cur无法向后移动。这是发现需要先定义一个临时的结点，先将cur.next保存下来，这样就可以把临时的结点复制给cur了。因此正确应该如图三。

图三

3.首先应该先初始化一个临时结点temp指向cur.next先保存下来，防止后续链接断开无法赋值。然后和上面操作一样，cur.next=pre,pre=cur,然后将临时结点复制给cur(cur=temp)，就使得整个链接连接起来并反转。

4.考虑一下终止条件，算法就写完了。随着不断重复①-④，不难发现当cur等于null时，前面所有的指针都实现了反转。算法完成。此时pre指向尾结点，返回pre即可。

代码如下：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
	  	//初始化双指针，cur表示当前头结点，pre为头结点的前一个结点
        ListNode cur = head;
        ListNode pre = null;
	  	//终止条件，cre == null，因此cur != null就一直循环
        while( cur != null ){
		  	//临时temp结点，保存cur的下一个结点，防止链表断了，无法指向
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

注意：cur.next = pre 和 pre = cur不能调换顺序。因为如果pre=cur在前执行，此时的pre引用就变了，cur和pre在一个位置了，此时再cur.next=pre就无法指向前一个节点了。

欢迎大家批评指点。