题解 | #反转链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        if(head == null){
            return null;
        }
        ListNode pre = null;
        ListNode nxt = null;

        while(head != null){
            nxt = head.next;
            head.next = pre;

            pre = head;
            head = nxt;
          
          //pre = pre.next;//wrong
          //head = head.next;



        }

        ListNode res = pre;
        
        
        
        return res;
    }
}

记录一下错误思路，大体就是遍历应在原链表，不应在新链表上。

含有伪代码的解释：

声明pre，nxt = null

原：pr head nxt

空 头节点 空

nxt = head.next；

pr head-> nxt

空 头 原头后1

head.next = pre

pr <- head nxt

新头后1 头 原头后1

之后遍历整个链表就行了，注意，是按照原链表的顺序进行迭代，去操作链表反转，先前已经处理过第一个头节点了，下一步要处理头节点后面的节点，也就是之前存的 nxt = head.next

pre = head；

head = nxt；

不能想当然地

pre = pre.next；

head = head.next；

因为链表已经改变，它在头节点处断开了，

比如

1->2->3->4->5在处理完第一次

nxt = head.next; head.next = pre;

时已经变成了

null<-1 2->3->4->5

pre = null; nxt = 2;

这样的话pre.next 和head.next除了前两次是null不能正常遍历之外，即使能遍历也是向相反方向，是不对的。