反转链表 java

系统管理员 2022-05-08 11:44 185阅读 0赞

## 反转链表 java ##

**题目描述**  
输入一个链表，反转链表后，输出新链表的表头。

> 代码1：

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode ReverseList(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode next = null;
            ListNode pre = null;
            for(; head != null; head = next){
                next = head.next;
                head.next = pre;
                pre = head;
            }
            return pre;
        }
    }

> 代码2：

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

> 代码3：非递归实现 – 推荐

import java.util.*;
    
    public class Solution {
        public void Mirror(TreeNode root) {
            if(root == null){
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()){
                //当栈不为 null 时出栈，交换左右子树
                TreeNode node = stack.pop();
                swap(node);
                if (node.left != null){
                    //左子树不为 null 入栈
                    stack.push(node.left);
                }
                if (node.right != null){
                    //右子树不为 null 入栈
                    stack.push(node.right);
                }
            }
        }
        
        public void swap(TreeNode root){
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }