链表反转(三种方式)

1. 指针变换

  public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode next = null;
        ListNode pre = null;
        ListNode newHead = null;
        while (cur != null) {
            next = cur.next;
            if (next == null) {
                newHead = cur;
            }
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return newHead;

    }

2. 结合栈

 public ListNode11 ReverseList(ListNode11 head) {
        if (head == null) {
            return null;
        }
        Stack<ListNode11> stack = new Stack<>();
        ListNode11 cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        ListNode11 newHead = new ListNode11(0);
        ListNode11 lastNode = newHead;

        ListNode11 curNode;
        while (!stack.isEmpty()) {
            curNode = stack.pop();
            lastNode.next = curNode;
            lastNode = lastNode.next;
        }

        return newHead.next;
    }

3. 递归

  public void ReverseList1(ListNode head) {
        if (head.next != null) {
            ReverseList1(head.next);
        }
        System.out.println(head);
    }