反转链表非递归的三种实现方式

题目：反转链表

1、Java代码：

import java.util.*;


public class Solution {
    public ListNode ReverseList(ListNode head) {
        Stack s_list = new Stack<>();
        
        while(head != null) {
            s_list.push(head);
            head = head.next;
        }
        
        if(s_list.isEmpty()) {
            return null;
        }
        
        ListNode pre = s_list.pop();
        ListNode cur_list = pre;
        while(!s_list.isEmpty()) {
            pre.next = s_list.pop();
            pre = pre.next;
        }

        pre.next = null;
        return cur_list;
    }
}

2、成环原因：栈存放的是链表节点，具有方向性，经过复杂变化以及指向，就成了环。

1、Java代码：

import java.util.*;


public class Solution {
    public ListNode ReverseList(ListNode head) {
        Stack s_list = new Stack<>();
        
        while(head != null) {
            s_list.push(head.val);
            head = head.next;
        }
        
        if(s_list.isEmpty()) {
            return null;
        }
        
        ListNode pre = new ListNode(s_list.pop());
        ListNode cur_list = pre;
        while(!s_list.isEmpty()) {
            pre.next = new ListNode(s_list.pop());
            pre = pre.next;
        }
//         pre.next = null;
        return cur_list;
    }
}

2、不成环原因：栈存放的是链表的值（val），然后再新建链表，将前面栈中存放的值作为val，自然不会有复杂的指向性，所以不会成环。

1、代码实现：

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode tmp = null;
        while(head != null) {
            tmp = head.next;
            head.next = pre;
            
            pre = head;
            head = tmp;
        }
        return pre;
    }
}

2、todo：是否也可以存放值，而非存放节点的做法进行实现？