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

0 反转链表

题目：反转链表

1 栈存放链表节点

1、Java代码：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;


public class Solution {
    public ListNode ReverseList(ListNode head) {
        Stack<ListNode> 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、成环原因：栈存放的是链表节点，具有方向性，经过复杂变化以及指向，就成了环。

2 栈存放链表节点的值

1、Java代码：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;


public class Solution {
    public ListNode ReverseList(ListNode head) {
        Stack<Integer> 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，自然不会有复杂的指向性，所以不会成环。

3 双链表方法

1、代码实现：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
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：是否也可以存放值，而非存放节点的做法进行实现？