Java反转单链表实战

算法是程序代码的灵魂!!!Java反转单链表这种算法一般会在面试中遇到,尤其是一些大公司!!!这里就来通过Java代码实战来讲解下实现反转的两种方法。

  1. 递归
  2. 普通遍历

这里介绍的两种方法都很常见,递归在算法里面非常常见!!

首先,我们要定义一个Node节点类:

public class Node{
    int value;
    Node nextNode;
    public Node(int value, Node nextNode) {
        super();
        this.value = value;
        this.nextNode = nextNode;
    }
}

因为是单链表,这里只有nextNode和当前节点的值。

我们这里初始化n个节点的链表,我们写一个初始化Node的方法:

/**
     * 初始化单链表
     * @param num 数量
     * @return
     */
    public static Node init(int num) {
        Node node = new Node(0, null);
        Node cur = null;
        Node temp = null;
        for(int i = 1 ; i < num;i++){
            temp = new Node(i, null);
            if (i == 1) {
                node.nextNode = temp;
            }else{
                cur.nextNode = temp;
            }
            cur = temp;
        }
        return node;
    }

然后,再把这个链表循环打印一下,先写一个out输出打印方法:

/**
     * 打印节点值
     * @param head
     */
    private static void out(Node head) {
        Node tempNode = head;
        while(tempNode != null){            
            System.err.println(tempNode.value);
            tempNode = tempNode.nextNode;
        }
    }

我们在main方法里面打印一下结果:

Node head = init(10);
out(head);

最后输出的结果值为:

0
1
2
3
4
5
6
7
8
9

普通遍历

/**
     * 反转单链表
     * @param head
     * @return
     */
    private static Node reverseHead(Node head) {
        if (head == null) {
            return head;
        }

        Node pre = head;
        Node cur = head.nextNode;
        Node next = null;
        while(cur != null){
            next = cur.nextNode;
            cur.nextNode = pre;

            pre = cur;
            cur = next;
        }
        head.nextNode = null;
        head = pre;
        return head;
    }

我们在main函数里调用下这个方法:

Node reverseHead = reverseHead(head);
out(reverseHead);

我们看下输出的结果值:

9
8
7
6
5
4
3
2
1
0

递归

/**
     * 递归反转
     * @param head
     * @return
     */
    private static Node reverseByRecur(Node current) {
        if (current == null || current.nextNode == null) return current;  
         Node nextNode = current.nextNode;  
         current.nextNode = null;  
         Node reverseRest = reverseByRecur(nextNode);  
         nextNode.nextNode = current;  
         return reverseRest;  
    }

我们在main函数里调用:

out(reverseByRecur(head));

我们看下输出的结果值:

9
8
7
6
5
4
3
2
1
0

两种方法都可以实现单链表反转,普通循环遍历容易理解一点,递归需要很强的逻辑性和思维性!!!