Java笔记 ·

单链表反转Java版

头插法与尾插法

本文主要用头插法实现单链表的反转,开始前先简单了解一下头插法与尾插法。

头插法:

在头节点的后面进行插入操作,后一个插入进来的值,在前一个插入进来的值与头节点之间。

尾插法:

设法找到插入结点的上一个结点,总而言之,尾插法就是要使后面插入的结点在前一个插入结点和NULL值之间。

链表反转

链表反转又可分为带逻辑头结点反转和不带逻辑头节点的反转,区别就是反转过程中是否单独设置一个逻辑头结点,具体可见代码。

设节点类为Node:

public static class Node{
    private int data;
    private Node next;

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    public int getData() {
        return data;
    }

    public void setNext(Node next) {
         this.next = next;
    }

    public Node getNext() {
        return next;
    }
}

为方便阅读,之后不再调用Node的Setters/Getters函数,直接用其属性。

带逻辑头节点的反转

/**
* 输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
* @param head
* @return
*/
public static Node reverseList_head(Node head) {
    // 创建一个临时结点,当作头插法的逻辑头结点
    Node root = new Node(0, null);
    // 逻辑头结点点的下一个结点为空
    root.next = null;
    // 用于记录要处理的下一个结点
    Node next;
    // 当前处理的结点不为空
    while (head != null) {
        // 记录要处理的下一个结点
        next = head.next;
        // 当前结点的下一个结点指向逻辑头结点的下一个结点
        head.next = root.next;
        // 逻辑头结点的下一个结点指向当前处理的结点
        root.next = head;
        // 上面操作完成了一个结点的头插
        // 当前结点指向下一个要处理的结点
        head = next;
    }
    // 逻辑头结点的下一个结点就是返回后的头结点
    return root.next;
}

不带逻辑头节点的反转

该函数中不再有上面代码中开头创建的临时节点root。

/**
* 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
* @param list
* @return
*/
public Node reverseList(Node list){
    if (list == null || list.getNext() == null) return list;
    // 用于记录当前处理的结点的
    Node curre = list;
    // 用于记录当前结点的前驱结点
    // 前驱结点开始为null,因为反转后的最后一个结点的下一个结点,即null
    // 也是反转链表的头结点
    Node pre = null;
    // 当前结点的下一个结点
    Node next = null;
    // 对链表进行头插法操作
    while (curre!=null){
        // 记录要处理的下一个结点
        next = curre.next;
        // 当前结点的下一个结点指向前驱结点,这样当前结点就插入到了反转链表的头部
        curre.next = pre;
        // 记录当前结点为前驱结点,完成一次头插
        pre = curre;
        // 当前结点指向下一个要处理的结点
        curre = next;
    }
    return pre;
}

再略微修改一下,可减少一次循环,本质上没区别,仅是因为最后一个结点肯定是反转后的头结点,所以省掉了最后一次循环:

public Node inverseLinkList(Node list){
    if (list == null || list.next == null) return list;

    Node pre = null;
    Node curre = list;
    Node next = null;

    while (curre.next!=null){
        next = curre.next;
        curre.next = pre;
        pre = curre;
        curre = next;
    }
    curre.next = pre;
    return curre;
}

参与评论