简单-Q206 反转链表

反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

• 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-linked-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Q206 {
  public static void main(String[] args) {
    ListNode node = new ListNode(1);
    ListNode root = node;
    for (int i = 2; i < 6; i++) {
      node.next = new ListNode(i);
      node = node.next;
    }
    print(root);
    ListNode node1 = new Q206().reverseList(root);
    print(node1);
  }
  // 迭代算法
  public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode current = head;
    while (current != null) {
      ListNode tmp = current.next;
      current.next = pre;
      pre = current;
      current = tmp;
    }
    return pre;
  }
  // 基于栈的解法
  public ListNode reverseList2(ListNode head) {
    if (head == null) {
      return head;
    }
    java.util.Stack<Integer> stack = new java.util.Stack<>();
    while (head != null) {
      stack.push(head.val);
      head = head.next;
    }
    ListNode startNode = new ListNode(stack.pop());
    ListNode tmpNode = startNode;
    while (!stack.empty()) {
      tmpNode.next = new ListNode(stack.pop());
      tmpNode = tmpNode.next;
    }
    return startNode;
  }
  static class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
    }
  }
  /**
   * 辅助方式，输出链表
   */
  private static void print(ListNode node) {
    System.out.print("[");
    while (node != null) {
      System.out.print(node.val + "->");
      node = node.next;
    }
    System.out.println("]");
  }
}