单向链表的翻转

写作目的

    链表的翻转为Leetcode第206道题目, 题目的地址为: https://leetcode.com/problems/reverse-linked-list/, 最开始的时候还稍微小看了这道题目, 原以为一两分钟就搞定了, 但是实际的解答过程中居然花了笔者十来分钟。可能是自己太掉以轻心了, 闲来无事，就记录一下，望各位看官指正。

节点类

public class LinkedNode {
    private LinkedNode next;
    private int value;

    public LinkedNode() {
    }

    public LinkedNode(int value) {
        this.value = value;
    }
    // setter and getter
}

链表的设计

LinkedNode tail = new LinkedNode(3);
LinkedNode middle = new LinkedNode(2);
LinkedNode head = new LinkedNode(1);

middle.setNext(tail);
head.setNext(middle);

System.out.println("=============未翻转之前==============");

LinkedNode current = head;

do{
    System.out.println(current.getValue());
}while((current = current.getNext()) != null);

具体的翻转方法

public static LinkedNode reverseList(LinkedNode head) {
    /**
     * current为当前遍历的节点
     * prev为上一个节点, 因为在循环的过程中需要当前节点next设置为上一个节点
     */
    LinkedNode current = head, prev = null;

    while(null != current) {
        //临时存储下一个节点
        LinkedNode curr = current.getNext();

        //设置当前节点的下一个节点为上一个节点
        current.setNext(prev);

        // 将设置了下个节点的当前节点存储起来，以便下次循环使用
        prev = current;

        //将临时存储起来的下一个节点赋值为current, 以便下一次循环使用
        current = curr;
    }
    //返回最后一个节点, 也就是翻转之后的第一个节点
    return prev;
}

链表的设计以及打印翻转之后的链表

public static void main( String[] args ) {
    LinkedNode tail = new LinkedNode(3);
    LinkedNode middle = new LinkedNode(2);
    LinkedNode head = new LinkedNode(1);

    middle.setNext(tail);
    head.setNext(middle);

    System.out.println("=============未翻转之前==============");

    LinkedNode current = head;

    do{
        System.out.println(current.getValue());
    }while((current = current.getNext()) != null);

    System.out.println("=============翻转之后=================");

    LinkedNode h = reverseList(head);  //翻转

    LinkedNode curr = h;

    do{
        System.out.println(curr.getValue());
    }while((curr = curr.getNext()) != null);
}

Leetcode上执行的结果

Snipaste_2020-03-08_20-54-47.png