博客

参考：





https://zhuanlan.zhihu.com/p/488188589

单链表结构

package com.luck.living.util;

import lombok.Data;

@Data
public class Linked {
    public Integer value;
    public Linked next;
}

逆转算法：

package com.luck.living.util;

/**
 * 参考：https://zhuanlan.zhihu.com/p/488188589
 */
public class LinkedUtil {

    /**
     * 1.迭代反转法
     * @param linked
     * @return
     */
    public static Linked reversalIteration(Linked linked) {
        if (linked == null || linked.next == null) {
            return linked;
        }
        Linked beg = null;
        Linked mid = linked;
        Linked end = linked.next;
        while (true) {
            mid.next = beg;
            if (end == null) {
                break;
            }
            beg = mid;
            mid = end;
            end = end.next;
        }
        return mid;
    }

    /**
     * 2.递归反转法
     * @param linked
     * @return
     */
    public static Linked reversalRecursion(Linked linked) {
        if (linked == null || linked.next == null) {
            return linked;
        }
        Linked newHead = LinkedUtil.reversalRecursion(linked.next);
        linked.next.next = linked;
        linked.next = null;
        return newHead;

    }
    /**
     * 3.头插法
     * @param linked
     * @return
     */
    public static Linked reversalHead(Linked linked) {
        if (linked == null || linked.next == null) {
            return linked;
        }
        Linked newLinked = null;
        Linked temp = null;
        while (linked != null) {
            temp = linked;           //旧链表头指针指向的结点放进temp
            linked = linked.next;    //头指针指向下一个结点，相当于上个结点已经剔除于链表之外，
            temp.next = newLinked;  //被剔除的结点从新链表头部插入
            newLinked = temp;        //新链表的头指针指向新加入的结点
        }
        return newLinked;
    }
    /**
     * 4.逆置法
     * @param linked
     * @return
     */
    public static Linked reversalInversion(Linked linked) {
        if (linked == null || linked.next == null) {
            return linked;
        }
        Linked beg = linked;
        Linked end = linked.next;
        while (end != null) {
            beg.next = end.next;
            end.next = linked;
            linked = end;
            end = beg.next;
        }
        return linked;
    }

    /**
     * 头插法
     * @return
     */
    public static Linked initHead() {
        Linked current = null;
        for (int i = 6; i >= 0; i--) {
            Linked next = new Linked();
            next.value = i;
            next.next = current;
            current = next;
        }
        System.out.println("初始化数据:" + current);
        return current;
    }
    public static Linked init() {
        Linked linked = new Linked();
        Linked begin = linked;
        for (int i = 0; i < 7; i++) {
            Linked next = new Linked();
            next.value = i;
            next.next = null;
            begin.next = next;
            begin = next;
        }
        System.out.println("初始化数据:" + linked.next);
        return linked.next;
    }

    public static void main(String[] args) {
        System.out.println("迭代反转法:" + LinkedUtil.reversalIteration(initHead()));
        System.out.println("递归反转法:" + LinkedUtil.reversalRecursion(initHead()));
        System.out.println("头插反转法:" + LinkedUtil.reversalHead(initHead()));
        System.out.println("原地逆置反转法:" + LinkedUtil.reversalInversion(initHead()));
    }
}