1. package top.ssyuan.easy;
    4. import java.util.ArrayList;
    5. import java.util.Stack;
    7. import top.ssyuan.Util;
    9. /**
    10.  * 206. Reverse Linked List
    11.  * Easy
    12.  * <p>
    13.  * 7972
    14.  * <p>
    15.  * 147
    16.  * <p>
    17.  * Add to List
    18.  * <p>
    19.  * Share
    20.  * Given the head of a singly linked list, reverse the list, and return the reversed list.
    21.  * <p>
    22.  * <p>
    23.  * <p>
    24.  * Example 1:
    25.  * <p>
    26.  * <p>
    27.  * Input: head = [1,2,3,4,5]
    28.  * Output: [5,4,3,2,1]
    29.  * Example 2:
    30.  * <p>
    31.  * <p>
    32.  * Input: head = [1,2]
    33.  * Output: [2,1]
    34.  * Example 3:
    35.  * <p>
    36.  * Input: head = []
    37.  * Output: []
    38.  */
    39. public class Lesson206 {
    41.     public static void main(String[] args) {
    42.         Lesson206 lesson = new Lesson206();
    43.         ListNode head = lesson.genLinkList(10);
    44.         lesson.printLink(head);
    45.         //head = new Solution1().reverseList(head);
    46.         head = new Solution2().reverseList(head);
    47.         Util.println("");
    48.         lesson.printLink(head);
    49.     }
    51.     private void printLink(ListNode head) {
    52.         ListNode node = head;
    53.         while (node != null) {
    54.             Util.print(node.val + "->");
    55.             node = node.next;
    56.         }
    57.     }
    59.     private ListNode genLinkList(int count) {
    60.         if (count < 1) return null;
    62.         ListNode head = new ListNode((int) (Math.random() * 100));
    63.         ListNode curNode = head;
    64.         for (int i = 1; i < count; i++) {
    65.             curNode.next = new ListNode((int) (Math.random() * 100));
    66.             curNode = curNode.next;
    67.         }
    69.         return head;
    70.     }
    73.     //Definition for singly-linked list.
    74.     public class ListNode {
    75.         int val;
    76.         ListNode next;
    78.         ListNode() {
    79.         }
    81.         ListNode(int val) {
    82.             this.val = val;
    83.         }
    85.         ListNode(int val, ListNode next) {
    86.             this.val = val;
    87.             this.next = next;
    88.         }
    89.     }
    91.     static class Solution1 {
    92.         public ListNode reverseList(ListNode head) {
    93.             if (head == null) {
    94.                 return null;
    95.             }
    97.             Stack<ListNode> nodes = new Stack<>();
    98.             ListNode node = head;
    99.             ListNode tmp;
    100.             while (node != null) {
    101.                 nodes.push(node);
    102.                 tmp = node;
    103.                 node = node.next;
    104.                 tmp.next = null;
    105.             }
    106.             head = nodes.pop();
    107.             node = head;
    108.             while (node != null && !nodes.isEmpty()) {
    109.                 node.next = nodes.pop();
    110.                 node = node.next;
    111.             }
    112.             return head;
    113.         }
    114.     }
    116.     static class Solution2 {
    117.         public ListNode reverseList(ListNode head) {
    118.             if (head == null) {
    119.                 return null;
    120.             }
    122.             ListNode node = head;
    123.             ListNode pre = null;
    124.             ListNode tmp = node;
    125.             while (node != null) {
    126.                 tmp = node;
    127.                 node = node.next;
    128.                 tmp.next = pre;
    129.                 pre = tmp;
    130.             }
    132.             return tmp;
    133.         }
    134.     }
    136. }