leetcode——反转链表

题目描述：
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

解题思路：
这里提供两个解题思路，迭代法和利用栈的方法
方法一、
迭代法就是依次反转链表的头结点指向即可，那点在于变换头结点指向时顺序别错了
方法二、
该思想是先创建一个栈，栈中存放链表的结点，依次入栈， 然后构造反链表时依次出栈组成新链表的顺序

代码实现：

方法一、
 public ListNode ReverseList(ListNode pHdead) {
        ListNode pre = null;   // 定义一个空结点
//        pre.next = pHdead; // 不需要，如果pHdead是空的话会出现空指针，
        ListNode cur = pHdead;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;  //
    }
     
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二、
public ListNode ReverseList2(ListNode head){
        Stack<ListNode>record = new Stack<>();
        ListNode temp = head;
        while(temp!=null){
            record.push(head);
            temp = temp.next;
        }
        if(record.empty()){
            return null;   // 处理极端情况
        }
        ListNode dummy = record.pop();  //赋初始值
        ListNode result = dummy;
        while(!record.empty()){
            ListNode tmp = record.pop();
            dummy.next = temp;
            dummy = dummy.next;
        }
        dummy.next = null;    // 最后一个结点是原链表的头节点，该节点的下一个节点指针指向第二个元素，为防止产生环形链表，所以最后一个元素的next要指向为空
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

总结：
1、作者在第一次解题时是用的第一种方法，当时存在一个错误，多写了一行代码(如图中被注释掉的那一行)， 那一行代码会直接使程序在编译阶段就报空指针的错误，以为不排除存在head是个空结点的情况.
对于方法一，需要理解的是while条件中的四个来回赋值的步骤，需要建立的理解的基础上才能够自己写出
2、对于方法二，作者在一开始实现的时候是创建了一个存放链表节点值的栈，显然这种做法是错误的，因为入栈之后再去构造新的链表时我们是没有完整的节点信息的，有的只是知道节点的值，需要我们一个个去构造链表结点，太麻烦了，还是将链表的节点入栈比较方便。
在使用方法二时需要注意特殊情况的处理，如栈为空说明链表本身即为空，需要直接返回；如最后一步将结点的下一个节点指向null，防止形成环形链表